From mccallum Mon Apr 5 12:48:13 1993 EDT To: Kresten Krab Thorup Subject: Collection library Hi Kresten, I'm willing to work on a Collection library. I just want to make sure that I'm not duplicating work. I think you had mentioned that you had started a Collection library. Would you like me to take it over (you seem so busy with all these other issues). Or, if you wanted I could just help you out with parts of it. In any case, I'd love to see what you've got so far. - Andrew From mccallum@cs.rochester.edu Sun Apr 11 15:38:41 1993 X-VM-Attributes: [nil nil nil nil nil] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA03808; Sun, 11 Apr 93 15:38:37 -0400 Received: from churchy.gnu.ai.mit.edu by cayuga.cs.rochester.edu (5.61/x) id AA28178; Sun, 11 Apr 93 15:38:32 -0400 Received: from cayuga.cs.rochester.edu by churchy.gnu.ai.mit.edu (5.65/4.0) with SMTP id ; Sun, 11 Apr 93 14:54:14 -0400 Received: from vein.cs.rochester.edu by cayuga.cs.rochester.edu (5.61/x) id AA28106; Sun, 11 Apr 93 14:54:05 -0400 Received: by vein.cs.rochester.edu (5.61/x) id AA20507; Sun, 11 Apr 93 14:54:03 -0400 Message-Id: <9304111854.AA20507@vein.cs.rochester.edu> In-Reply-To: <199304111329.AA29361@xiv.iesd.auc.dk> From: mccallum@cs.rochester.edu To: Kresten Krab Thorup Cc: gnu-objc@gnu.ai.mit.edu Subject: A Collection heirarchy Date: Sun, 11 Apr 93 14:54:03 -0400 Hi Kresten, I don't have time at the moment to write everything I wanted to say about Collection object issues, but here is a start: ---------- 8< ------------- A Smalltalk-like Collection heirarchy for Objective C Objective C is not Smalltalk. Differences that matter to the Collection heirarchy: - There can be only one set of argument types with each selector. (For instance in Objective C we can't have "-(double)data" and "-(char)data". I can't stand it when some library that I'm forced to load already defines a selector that I want to use with different types.) This isn't an issue in Smalltalk because everything is an object. * I propose to make the Collection method names a little more descriptive, while keeping them as close to Smalltalk as possible. (For instance I think there is a good reason for using "-addObject:" instead of "-add:") - We will want collections of int's, float's, and other non-Objects. Using Objective C wrappers around these C primitive types (i.e. Integer and Float objects) is not an efficient enough option for all cases. * We could create two parallel heirarchies, one for Objects and one for elements passed as void*, but so much of the functionality overlaps, I propose that we merge them. From what I've tried so far it doesn't actually look all that bad. - Objective C doesn't have Smalltalk Blocks. * Passing selectors and pointers to functions are both reasonable substitutes. I propose making both options available. They are distinguished as "-detectByFunc:" and "-detectBySel:" for example. - Smalltalk does automatic garbage collection; Objective C doesn't. * I think it should be made more obvious which methods allocate a new object. Hence "-copyAsBag" instead of "asBag", and "-copySelect..." instead of "-select...". - We should have usable Collection classes (Set, Bag, Array, etc) with functionality matching Smalltalk's objects, but there may be good reasons for not having the abstract superclass structure match Smalltalk exactly. * <> NOTES: Could do everything with methods named "...Element", but having some parallel methods named "...Object" saves the programmer from having to cast return values, and it might be a little more esthetically pleasing. It will also allow code written for a NeXT to port more nicely. (Our Array class could respond to a superset of methods from NeXT's List class.) ---------- 8< ------------ Here's the current state of Collection.h. I've looked at Smalltalk, the NIHCL (National Institutes of Health C++ class library which includes a Collection heirarchy), the collection heirarchy inside of Diagram2.0 (it's quite exciting! take a look at FCCollection and its subclasses using AppInspector), and at NeXT's collection objects. BTW, I've send email to the people at Lighthouse Design three times asking them about the possibility of donating their FCCollection classes to GNU, but I've gotten no reply. --------- 8< ---------- #include typedef void (*CollectionFunc)(void *); typedef BOOL (*BoolCollectionFunc)(void *); typedef id (*IdCollectionFunc)(void *); typedef void (*CollectionFunc2)(void *, void *); @interface Collection : Object { char *_description; } /* Instance creation */ + with:(void *)anElement; + with:(void *)firstElement with:(void *)secondElement; + with:(void *)firstElement with:(void *)secondElement with:(void *)thirdElement; /* Initializing and freeing */ - initCapacity: (unsigned)aCapacity description:(const char *)type - initCapacity: (unsigned)aCapacity; - initDescription:(const char *)type - init; - free; - freeElements; /* Adding */ - addElement: (void *)newElement; - addElementIfAbsent: (void *)newElement; - addElementsFrom: (id )aCollection; - addElementsIfAbsentFrom: (id )aCollection; /* Removing and replacing */ /* What should be returned for all these methods? */ - (void *) removeElement: (void *)oldElement; - (void *) removeAllOccurancesOfElement: (void *)oldElement; - (void *) removeElementsIn: (id )aCollection; - removeElementsNotIn: (id )aCollection; - replaceElement: (void *)oldElement with: (void *)newElement; - replaceAllOccurancesOfElement: (void *)oldElement with: (void *)newElement; - empty; /* Testing */ - (BOOL) includesElement: (void *)anElement; - (BOOL) includesSubsetOf: (id )aCollection; - (BOOL) includesSameContentsAs: (id )aCollection; - (BOOL) isDisjointFrom: (id )aCollection; - (BOOL) isEmpty; - (unsigned) occurrencesOf: (void *)anElement; - (BOOL) trueForAllByFunc: (BoolCollectionFunc)aFunc; - (BOOL) trueForAllBySel: (SEL)aBoolSel; - (BOOL) trueForAllBySel: (SEL)aBoolSel with: (void *)argElement; - (BOOL) trueForAllBySel: (SEL)aBoolSel in: selElement; - (BOOL) trueForAllBySel: (SEL)aBoolSel in: selElement with: (void *)argElement; - (BOOL) trueForAnyByFunc: (BoolCollectionFunc)aFunc; - (BOOL) trueForAnyBySel: (SEL)aBoolSel; - (BOOL) trueForAnyBySel: (SEL)aBoolSel with: (void *)argElement; - (BOOL) trueForAnyBySel: (SEL)aBoolSel in: selObject; - (BOOL) trueForAnyBySel: (SEL)aBoolSel in: selObject with: (void *)argElement; /* Iterating */ - doByFunc: (CollectionFunc)aFunc untilYes:(BOOL *)flag; - doByFunc: (CollectionFunc)aFunc; - doOnShallowCopyByFunc: (CollectionFunc)aFunc untilYes:(BOOL *)flag; - doOnShallowCopyByFunc: (CollectionFunc)aFunc; - doBySel: (SEL)aSel; - doBySel: (SEL)aSel with: (void *)argElement; - doBySel: (SEL)aSel in: selObject; - doBySel: (SEL)aSel in: selObject with: (void *)argElement; - makeObjectsPerform: (SEL)aSel; - makeObjectsPerform: (SEL)aSel with: (void *)argElement; /* Copying */ - shallowCopy; - shallowCopyAs: aCollectionClass; - deepen; /* Copying enumerators */ - copySelectByFunc: (BoolCollectionFunc)aFunc; - copySelectBySel: (SEL)aBoolSel; - copySelectBySel: (SEL)aBoolSel with: (void *)argElement; - copySelectBySel: (SEL)aBoolSel in: selObject; - copySelectBySel: (SEL)aBoolSel in: selObject with: (void *)argElement; - copyRejectByFunc: (BoolCollectionFunc)aFunc; - copyRejectBySel: (SEL)aBoolSel; - copyRejectBySel: (SEL)aBoolSel with: (void *)argElement; - copyRejectBySel: (SEL)aBoolSel in: selObject; - copyRejectBySel: (SEL)aBoolSel in: selObject with: (void *)argElement; - copyCollectByFunc: (IdCollectionFunc)aFunc; - copyCollectBySel: (SEL)aSel; - copyCollectBySel: (SEL)aSel with: (void *)argElement; - copyCollectBySel: (SEL)aSel in: selObject; - copyCollectBySel: (SEL)aSel in: selObject with: (void *)argElement; /* Non-copying enumerators */ - (void *) detectByFunc: (BoolCollectionFunc)aFunc; - (void *) detectBySel: (SEL)aBoolSel; - (void *) detectBySel: (SEL)aBoolSel with: (void *)argElement; - (void *) detectBySel: (SEL)aBoolSel in: selObject; - (void *) detectBySel: (SEL)aBoolSel in: selObject with: (void *)argElement; - inject: (void *)initialData byFunc: (IdCollectionFunc2)aFunc; - inject: (void *)initialData bySel: (SEL)aSel into: selObject; - uniqueElements; @end --------- 8< ---------- The only subclass responsibilities are - addElement; - removeElement; - doByFunc:untilYes: although obviously will will want to override some of these for efficiency; and obviously we will add more methods in subclasses such as SeqCollection. I welcome any and all suggestions, comments, complaints about completely wrong approach, etc... Regards, Andrew P.S. Kresten, I've made some changes to my List object because it wasn't actually compatible with NeXT's List object in several ways. I was going to release my changes, but I wanted to test it a little more before I did so. Do you have any code for testing List's and HashTable's? -------------------------------------------------------------- R. Andrew McCallum ARPA: mccallum@cs.rochester.edu Computer Science Department UUCP: uunet!cs.rochester.edu!mccallum University of Rochester VOX: (716) 275-2527 Rochester, NY 14627-0226 FEET: CSB Rm. 625 From krab@iesd.auc.dk Sun Apr 11 15:57:37 1993 X-VM-Attributes: [nil nil nil nil nil] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA04394; Sun, 11 Apr 93 15:57:33 -0400 Received: from iesd.auc.dk by cayuga.cs.rochester.edu (5.61/x) id AA28224; Sun, 11 Apr 93 15:57:30 -0400 Received: from xiv.iesd.auc.dk by iesd.auc.dk with SMTP id AA13745 (5.65c8/IDA-1.5/MD for ); Sun, 11 Apr 1993 21:51:27 +0200 Received: by xiv.iesd.auc.dk id AA00947 (5.65c8/IDA-CLIENT/MD); Sun, 11 Apr 1993 21:51:51 +0200 Message-Id: <199304111951.AA00947@xiv.iesd.auc.dk> From: Kresten Krab Thorup To: mccallum@cs.rochester.edu Cc: krab@iesd.auc.dk, gnu-objc@gnu.ai.mit.edu Subject: Re: A Collection heirarchy Date: Sun, 11 Apr 1993 21:51:51 +0200 I've used this sunday for cleaning up / rewriting my collection library. This is pretty close to Smalltalk, although I've not made a nice inheritance hierachy -- I intend to make a nice protocol hierachy instead. I hope to make a *alpha alpha* release version -200 later today, and then we could discuss details relative to that -- I'm open for throwing the whole thing away if that's really desireable :-) * I propose to make the Collection method names a little more descriptive, while keeping them as close to Smalltalk as possible. (For instance I think there is a good reason for using "-addObject:" instead of "-add:") This is a good idea. I'll follow this. * We could create two parallel heirarchies, one for Objects and one for elements passed as void*, but so much of the functionality overlaps, I propose that we merge them. From what I've tried so far it doesn't actually look all that bad. Hmm. I don't really like this -- a lot of code will be obscured and slowed down by this. I'd rather make seperate classes e.g. IdArray vs StringArray, and then live with the copying of code. It is somewhat important that the code is clean and efficient, as it'll be an example for newcomers. * Passing selectors and pointers to functions are both reasonable substitutes. I propose making both options available. They are distinguished as "-detectByFunc:" and "-detectBySel:" for example. This is ok -- I already use local (nested) functions a lot in my code. This makes the code very neat, e.g. the generic implementation of `-select': - select: (SEL)aSelector { id newCollection = [[self species] new]; void doSelect (id elem) { if ([elem perform: aSelector]) [newCollection add: elem]; } [self withElementsCall: doSelect]; return newCollection; } - We should have usable Collection classes (Set, Bag, Array, etc) with functionality matching Smalltalk's objects, but there may be good reasons for not having the abstract superclass structure match Smalltalk exactly. * <> Well, good arguments are efficiency. The classes can still have nice conceptual associations via protocols. /Kresten From krab@iesd.auc.dk Sun Apr 11 18:50:46 1993 X-VM-Attributes: [nil nil nil nil t] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA09418; Sun, 11 Apr 93 18:50:42 -0400 Received: from iesd.auc.dk by cayuga.cs.rochester.edu (5.61/x) id AA28568; Sun, 11 Apr 93 18:50:38 -0400 Received: from xiv.iesd.auc.dk by iesd.auc.dk with SMTP id AA14633 (5.65c8/IDA-1.5/MD for ); Mon, 12 Apr 1993 00:46:39 +0200 Received: by xiv.iesd.auc.dk id AA01811 (5.65c8/IDA-CLIENT/MD); Mon, 12 Apr 1993 00:47:02 +0200 Message-Id: <199304112247.AA01811@xiv.iesd.auc.dk> From: Kresten Krab Thorup To: mccallum@cs.rochester.edu Cc: krab@iesd.auc.dk, gnu-objc@gnu.ai.mit.edu Subject: Collection library Date: Mon, 12 Apr 1993 00:47:02 +0200 If anyone would like to comment it, here's something on my collection library. The following is the interface specs @protocol Collection // ALLOCATION/MANAGEMENT + newCapacity: (unsigned)initialSize; - initCapacity: (unsigned)initialSize; - freeContents; // Create a new collection initially containing specified object(s) + withObject: anObject; + withObject: firstObject with: secondObject; // ADDING - addObject: anObject; - addAllObjects: aCltn; // REMOVING - removeObject: anObject; - removeAllObjects: aCltn; // TESTING - (BOOL)isEmpty; - (BOOL)includesObject: anObject; - (unsigned) occurrencesOfObject: anObject; // ACCESSING - (unsigned) size; // ENUMERATION // Send aSelector to each object in the collection. - makeObjectsPerform: (SEL)aSelector; - makeObjectsPerform: (SEL)aSelector with: anObject; // Send aSelector to anObject with argument each object in turn. - withObjectsPerform: (SEL)aSelector on: anObject; - withObjectsPerform: (SEL)aSelector on: anObject with: secondObject; // Apply aFunction to each object in the collection - withObjectsCall: (void(*)(id)) aFunction; - withObjectsCall: (void(*)(id, id)) aFunction with: anObject; // Return a new collection keeping the results of performing aSelector // on each object in turn - map: (SEL)aSelector; - map: (SEL)aSelector with: anObject; // Return the first object which answers "YES" when sent the selector // aSelector. Otherwise return nil. - detect: (SEL)aSelector; - detect: (SEL)aSelector with: anObject; // Return a new collection of all the objects currently in the receiver, // which answers "NO" when sent aSelector - reject: (SEL)aSelector; - reject: (SEL)aSelector with: anObject; // Return a new collection of all the objects currently in the receiver, // which answers "YES" when sent aSelector - select: (SEL)aSelector; - select: (SEL)aSelector with: anObject; @end @protocol MappedCollection // ACCESSING // Return object mapped by the object aKey - atObject: aKey; // Insert anObject mapped by aKey - at: aKey putObject: anObject; // Return 's containing either all key or value objects - objectKeys; - objectValues; // ENUMERARTION // For each value object in turn, call aFunction with that // object as argument. -withObjectsCall has the same behaviour - withValuesCall: (void(*)(id))aFunction; - withValuesCall: (void(*)(id, id))aFunction with: anObject; // For each key object in turn, call aFunction with that // object as argument. - withKeysCall: (void(*)(id))aFunction; - withKeysCall: (void(*)(id, id))aFunction with: anObject; // For each key object in turn, send aSelector to that object - makeKeysPerform: (SEL)aSelector; - makeKeysPerform: (SEL)aSelector with: anObject; @end @protocol SequencedCollection // ACCESSING // Return object at specified index - objectAtIndex: (unsigned)anIndex; // Return index corresponding to anObject - (unsigned) indexOfObject: anObject; // ADDING - atIndex: (unsigned)anIndex putObject: anObject; // REMOVING - removeObjectAtIndex: (unsigned)anIndex; @end @protocol ArrayedCollection // ACCESSING // Get or set the maximum capacity for the ArrayedCollection - (unsigned) capacity; - setCapacity: (unsigned)anInteger; @end @protocol Link + nextLink: aLink; /* create a Link linked to `aLink' */ - nextLink; /* return next link */ - nextLink: aLink; /* assign next link */ @end The following classes are currently present. All classes manipulate *objects* only. I've not written anything to handle simple types yet. Collection Abstract class, which implements "generic" methods. It cannot actually contain anything ... Set Can contain one of each object. Elements are kept in a hash table. Bag Can contain several of each object. Elements are kept in a hash table mapping object to number of occurrences. Dictionary Maps key objects to value objects. This is mostly like a hash table. LinkList A singly linked list of objects conforming to the protocol. That is in principle objects inheriting "Link" This makes house keeping a lot cheaper. LinkedList A singly linked list of any kind of objects. Array A simple "List" like collection. If you want the sources you can pick them up from iesd.auc.dk: /pub/ObjC/libcoll.tar.z. You cannot compile it though, since it uses features of GNU Objective C not yet public available -- soon to come! I have not tested it at all -- this is "rough source", but I'll go to bed now, so hopefully there'll be some comments tomorrow :-) Comments appreciated! /Kresten From mccallum@cs.rochester.edu Sun Apr 11 22:57:37 1993 X-VM-Attributes: [nil nil nil nil nil] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA16865; Sun, 11 Apr 93 22:57:33 -0400 Received: from churchy.gnu.ai.mit.edu by cayuga.cs.rochester.edu (5.61/x) id AA29017; Sun, 11 Apr 93 22:57:29 -0400 Received: from cayuga.cs.rochester.edu by churchy.gnu.ai.mit.edu (5.65/4.0) with SMTP id ; Sun, 11 Apr 93 22:19:12 -0400 Received: from vein.cs.rochester.edu by cayuga.cs.rochester.edu (5.61/x) id AA28973; Sun, 11 Apr 93 22:19:09 -0400 Received: by vein.cs.rochester.edu (5.61/x) id AA23109; Sun, 11 Apr 93 22:19:08 -0400 Message-Id: <9304120219.AA23109@vein.cs.rochester.edu> In-Reply-To: <199304112247.AA01811@xiv.iesd.auc.dk> From: mccallum@cs.rochester.edu To: Kresten Krab Thorup Cc: gnu-objc@gnu.ai.mit.edu Subject: Re: Collection library Date: Sun, 11 Apr 93 22:19:08 -0400 Hi Kresten, I'm glad that we're both working on Collection class issues. I'm also open to throwing my whole thing away if it turns out that it's desirable. Whichever way we end up going in the end, I think that we'll finish with a better result by hacking out more than one experimental implementation. I think our biggest point of difference is in the "Collections holding arbitrary 32-bit quantities" vs "Separate Collection classes for different non-objects". My idea is based on NeXT's HashTables. They aren't too ugly, and it sure would be a pain if you had to use a different class for each key type (integers, floats, char*'s, etc). The implementation overlap between collections of objects and non-objects is phenomenal! The great majority of my code doesn't even have to know if the element it is dealing with is an object or not. The places where the two are treated differently is mostly encapsulated in the Collection instance's "compare" and "hash" functions (just like HashTable). The only other place it matters is in some error checking for things like "makeObjectsPerform:" to make sure that the Collection does hold objects. You didn't comment on my proposal for discriminating methods that return new copies. I think it may get pretty confusing to look at the result of a "select:" getting freed, when beginners are trained to expect that most methods return self (unless the method name makes you think otherwise). Using these names exactly as used in Smalltalk is only going to make the former Smalltalk users feel at home, but Smalltalk doesn't even have a concept of freeing. A few comments on your last message: * I like your idea of using a heirarchy of protocols. * I would think that we would want to pass functions with "select:", and its cousins. It may be rare that the objects in the collection happen to respond to some boolean method with just the features we are interested in. As I mentioned before, I think providing for selectors as well is a good idea. * What's the reason for putting a reference to "capacity" in the base Collection protocol? They are not relevant to LinkedList's at all, for instance. (This seems like a leftover from Smalltalk Object's indexed instance vars?) * ' just wondering why you used the name "map:" instead of "collect:" ("collect:" would match with Smalltalk, as do the rest of your select, reject, and detect methods.) * I notice your Link and LinkList stuff. Does this mean you are doing object creation / destruction each time you do an add or remove to that collection? I know that Smalltalk has Link objects, but do we really want to do this in Objective C? ** I think we may have slightly different approaches to this implementation. Perhaps the difference I'm thinking of was shown most clearly when you said, "It is somewhat important that the code is clean and efficient, *as it'll be an example for newcomers.*" [emphasis mine]. I believe we should implement the Collection heirarchy to be as efficient and powerful as possible; and the best implementation may not end up being the perfect example of Objective C *for newcomers*. We can distribute other example programs for that. For example, the "Link" objects are a great example of OO programming for beginners to study, but I don't think they are the most efficient way to implement LinkedList's for Objective C. Having our Collection classes hold arbitrary 32-bit quantities may not produce the best Objective tutorial, but they would be powerful and efficient. Again, I welcome any and all suggestions, comments, complaints. Regards, Andrew -------------------------------------------------------------- R. Andrew McCallum ARPA: mccallum@cs.rochester.edu Computer Science Department UUCP: uunet!cs.rochester.edu!mccallum University of Rochester VOX: (716) 275-2527 Rochester, NY 14627-0226 FEET: CSB Rm. 625 From burchard@geom.umn.edu Mon Apr 12 13:28:03 1993 X-VM-Attributes: [nil nil nil nil nil] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA10990; Mon, 12 Apr 93 13:27:59 -0400 Received: from cameron.geom.umn.edu by cayuga.cs.rochester.edu (5.61/x) id AA01325; Mon, 12 Apr 93 13:27:57 -0400 Received: from mobius.geom.umn.edu by cameron.geom.umn.edu; Mon, 12 Apr 1993 12:24:36 -0500 Message-Id: <9304121724.AA04796@mobius.geom.umn.edu> Received: by mobius.geom.umn.edu; Mon, 12 Apr 93 12:24:35 -0500 Received: by NeXT.Mailer (1.87.1) Received: by NeXT Mailer (1.87.1) From: burchard@geom.umn.edu To: Kresten Krab Thorup Cc: mccallum@cs.rochester.edu, gnu-objc@gnu.ai.mit.edu Subject: Re: Collection library Date: Mon, 12 Apr 93 12:24:35 -0500 One thing that would probably be a good addition to the collection protocols---in light of the archiving dilemmas encountered by others with the List class---would be ways to specify whether the collection owns the objects in it or not: - setOwner:(BOOL)flag; // default is NO - (BOOL)isOwner; isOwner==YES would imply: * freeing the collection frees any objects remaining in it * archiving the collection writes the objects it contains directly (not as references) * copying the collection does one of the following, as appropriate (in its -deepen method, which checks if isOwner==YES): -- copies the objects inside it -- adds a reference count to the objects inside it -- makes the copied collection non-owner As usual, this issue is a side effect of not having garbage collection. -------------------------------------------------------------------- Paul Burchard ``I'm still learning how to count backwards from infinity...'' -------------------------------------------------------------------- From pages!kevin@uunet.UU.NET Mon Apr 12 15:38:09 1993 X-VM-Attributes: [nil nil nil nil nil] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA14059; Mon, 12 Apr 93 15:38:02 -0400 Received: from churchy.gnu.ai.mit.edu by cayuga.cs.rochester.edu (5.61/x) id AA01942; Mon, 12 Apr 93 15:37:59 -0400 Received: from relay2.UU.NET by churchy.gnu.ai.mit.edu (5.65/4.0) with SMTP id ; Mon, 12 Apr 93 14:44:46 -0400 Received: from spool.uu.net (via LOCALHOST.UU.NET) by relay2.UU.NET with SMTP (5.61/UUNET-internet-primary) id AA26591; Mon, 12 Apr 93 14:42:37 -0400 Received: from pages.UUCP by spool.uu.net with UUCP/RMAIL (queueing-rmail) id 143654.771; Mon, 12 Apr 1993 14:36:54 EDT Received: from planet10 by pages.com (NX5.67c/NX3.0M) id AA08967; Mon, 12 Apr 93 11:31:56 -0700 Message-Id: <9304121831.AA08967@pages.com> Received: by planet10. (NX5.67c/NX3.0X) id AA00357; Mon, 12 Apr 93 11:31:56 -0700 Received: by NeXT.Mailer (1.87.1) Received: by NeXT Mailer (1.87.1) From: Kevin Sven Berg To: gnu-objc@gnu.ai.mit.edu Subject: re: Collection library Date: Mon, 12 Apr 93 11:31:56 -0700 re: "setOwner:" proposal We've taken the approach of providing a "write contents as reference" function when dealing with lists. This requires no extra storage in the collection object (important when you get lots of them), and the implementor can use either type of function. It also is somewhat like what Kresten proposed... NXWriteObject <-> NXReadObject NXWriteObjectReference <-> NXReadObjectReference (must match; KKT proposal) WriteReferenceList <-> ReadReferenceList ** Comments? Kevin From athan@object.com Mon Apr 12 16:55:17 1993 X-VM-Attributes: [nil nil nil nil nil] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA15944; Mon, 12 Apr 93 16:55:11 -0400 Received: from churchy.gnu.ai.mit.edu by cayuga.cs.rochester.edu (5.61/x) id AA02226; Mon, 12 Apr 93 16:55:07 -0400 Received: from relay1.UU.NET by churchy.gnu.ai.mit.edu (5.65/4.0) with SMTP id ; Mon, 12 Apr 93 16:07:59 -0400 Received: from spool.uu.net (via localhost.UU.NET) by relay1.UU.NET with SMTP (5.61/UUNET-internet-primary) id AA15299; Mon, 12 Apr 93 16:06:12 -0400 Received: from lissie.UUCP by spool.uu.net with UUCP/RMAIL (queueing-rmail) id 160517.23502; Mon, 12 Apr 1993 16:05:17 EDT Received: from swing by lissie.object.com (NX5.67c/NeXT-2.0abc) id AA20632; Mon, 12 Apr 93 15:21:35 -0400 Received: by swing.object.com (NX5.67c/NeXT-2.0) id AA01440; Mon, 12 Apr 93 15:21:34 -0400 Message-Id: <9304121921.AA01440@ swing.object.com > Received: by NeXT.Mailer (1.87.1) Received: by NeXT Mailer (1.87.1) From: athan@object.com (Andrew Athan) To: Kevin Sven Berg Cc: gnu-objc@gnu.ai.mit.edu Subject: Re: Collection library Date: Mon, 12 Apr 93 15:21:34 -0400 Kevin Sven Berg writes: > NXWriteObject <-> NXReadObject > NXWriteObjectReference <-> NXReadObjectReference (must match; KKT proposal) > WriteReferenceList <-> ReadReferenceList ** > What is NXReadObjectReference? It does not exist in the NeXT AppKit. I don't see a need for a "ReadObjectReference" function--NXReadObject can be implemented such that it returns the same id for all references to some object from the same stream. Andrew Athan Objective Technologies, Inc. From burchard@geom.umn.edu Mon Apr 12 17:34:57 1993 X-VM-Attributes: [nil nil nil nil nil] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA16793; Mon, 12 Apr 93 17:34:51 -0400 Received: from churchy.gnu.ai.mit.edu by cayuga.cs.rochester.edu (5.61/x) id AA02367; Mon, 12 Apr 93 17:34:47 -0400 Received: from cameron.geom.umn.edu by churchy.gnu.ai.mit.edu (5.65/4.0) with SMTP id ; Mon, 12 Apr 93 16:52:22 -0400 Received: from mobius.geom.umn.edu by cameron.geom.umn.edu; Mon, 12 Apr 1993 15:20:51 -0500 Message-Id: <9304122020.AA04893@mobius.geom.umn.edu> Received: by mobius.geom.umn.edu; Mon, 12 Apr 93 15:20:45 -0500 Received: by NeXT.Mailer (1.87.1) Received: by NeXT Mailer (1.87.1) From: burchard@geom.umn.edu To: Kevin Sven Berg Cc: gnu-objc@gnu.ai.mit.edu Subject: Re: Collection library Date: Mon, 12 Apr 93 15:20:45 -0500 > We've taken the approach of providing a "write contents > as reference" function when dealing with lists. This > requires no extra storage in the collection object This is fine as long as everyone handling lists "knows" which lists are supposed to be treated as a reference lists and which are not. But that wouldn't seem to be the case in many situations; for example if the list is passed as a parameter in a distributed object message. If the extra storage is painful, you can always just make one type of list be a subclass of the other. (This is, after all, another version of the old problem of losing static type information.) -------------------------------------------------------------------- Paul Burchard ``I'm still learning how to count backwards from infinity...'' -------------------------------------------------------------------- From pages!kevin@uunet.UU.NET Mon Apr 12 17:45:24 1993 X-VM-Attributes: [nil nil nil nil nil] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA16953; Mon, 12 Apr 93 17:45:17 -0400 Received: from churchy.gnu.ai.mit.edu by cayuga.cs.rochester.edu (5.61/x) id AA02396; Mon, 12 Apr 93 17:45:14 -0400 Received: from relay1.UU.NET by churchy.gnu.ai.mit.edu (5.65/4.0) with SMTP id ; Mon, 12 Apr 93 17:11:07 -0400 Received: from spool.uu.net (via localhost.UU.NET) by relay1.UU.NET with SMTP (5.61/UUNET-internet-primary) id AB05573; Mon, 12 Apr 93 17:08:33 -0400 Received: from pages.UUCP by spool.uu.net with UUCP/RMAIL (queueing-rmail) id 170706.10022; Mon, 12 Apr 1993 17:07:06 EDT Received: from planet10 by pages.com (NX5.67c/NX3.0M) id AA09690; Mon, 12 Apr 93 14:01:30 -0700 Message-Id: <9304122101.AA09690@pages.com> Received: by planet10. (NX5.67c/NX3.0X) id AA00517; Mon, 12 Apr 93 14:01:29 -0700 Received: by NeXT.Mailer (1.87.1) Received: by NeXT Mailer (1.87.1) From: Kevin Sven Berg To: athan@object.com (Andrew Athan) Cc: gnu-objc@gnu.ai.mit.edu Subject: Collection library Date: Mon, 12 Apr 93 14:01:29 -0700 >>Kevin Sven Berg writes: >> >> NXWriteObject <-> NXReadObject >> NXWriteObjectReference <-> NXReadObjectReference (must match; KKT >>proposal) >> WriteReferenceList <-> ReadReferenceList ** >> > > athan@object.com (Andrew Athan) writes: > >What is NXReadObjectReference? It does not exist in the NeXT AppKit. I don't >see a need for a "ReadObjectReference" function--NXReadObject can be >implemented such that it returns the same id for all references to some object >from the same stream. Nope, you won't find it in any NeXT manual. Note that the line is followed by "proposal". Kresten proposed doing symmetric read/write reference functions. I proposed exactly the same thing for collections, and gave an example of how we [Pages] actually are using this symmetry right now for lists (last pairing -- the **'s). regards, Kevin From krab@iesd.auc.dk Mon Apr 12 18:30:34 1993 X-VM-Attributes: [nil nil nil nil nil] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA17734; Mon, 12 Apr 93 18:30:27 -0400 Received: from churchy.gnu.ai.mit.edu by cayuga.cs.rochester.edu (5.61/x) id AA02525; Mon, 12 Apr 93 18:30:24 -0400 Received: from iesd.auc.dk by churchy.gnu.ai.mit.edu (5.65/4.0) with SMTP id ; Mon, 12 Apr 93 17:59:14 -0400 Received: from xiv.iesd.auc.dk by iesd.auc.dk with SMTP id AA21830 (5.65c8/IDA-1.5/MD for ); Mon, 12 Apr 1993 23:58:22 +0200 Received: by xiv.iesd.auc.dk id AA07240 (5.65c8/IDA-CLIENT/MD); Mon, 12 Apr 1993 23:58:47 +0200 Message-Id: <199304122158.AA07240@xiv.iesd.auc.dk> From: Kresten Krab Thorup To: gnu-objc@gnu.ai.mit.edu Cc: krab@iesd.auc.dk Subject: read_reference Date: Mon, 12 Apr 1993 23:58:47 +0200 The reson for having matching read/write reference was to make clear that a reference "read" may not be accessible at once, this is not guaranteed before -awake is called. It is not an implementation issue -- in fact my current implementation doesnt have read_reference at all. /Kresten From krab@iesd.auc.dk Mon Apr 12 19:17:25 1993 X-VM-Attributes: [nil nil nil nil t] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA18684; Mon, 12 Apr 93 19:17:19 -0400 Received: from iesd.auc.dk by cayuga.cs.rochester.edu (5.61/x) id AA02626; Mon, 12 Apr 93 19:17:15 -0400 Received: from xiv.iesd.auc.dk by iesd.auc.dk with SMTP id AA22364 (5.65c8/IDA-1.5/MD for ); Tue, 13 Apr 1993 01:14:06 +0200 Received: by xiv.iesd.auc.dk id AA07462 (5.65c8/IDA-CLIENT/MD); Tue, 13 Apr 1993 01:14:32 +0200 Message-Id: <199304122314.AA07462@xiv.iesd.auc.dk> In-Reply-To: <9304120219.AA23109@vein.cs.rochester.edu> (mccallum@cs.rochester.edu) From: Kresten Krab Thorup To: mccallum@cs.rochester.edu Cc: gnu-objc@gnu.ai.mit.edu Subject: Re: Collection library Date: Tue, 13 Apr 1993 01:14:32 +0200 My idea is based on NeXT's HashTables. They aren't too ugly, and it sure would be a pain if you had to use a different class for each key type (integers, floats, char*'s, etc). Ok, I'll look into how to code this. Should we use "Object" suffix for id'ish selectors and "Element" for all others? This way we'll have typechecking at least on objects... Using these names exactly as used in Smalltalk is only going to make the former Smalltalk users feel at home, but Smalltalk doesn't even have a concept of freeing. Well, you're right, but "copy" is not the right verb here.. We should come up with something better. * I would think that we would want to pass functions with "select:", and its cousins. It may be rare that the objects in the collection happen to respond to some boolean method with just the features we are interested in. As I mentioned before, I think providing for selectors as well is a good idea. Right -- perhaps we should even have 3 variants "selectByPerforming:", "selectByPerforming:on:" and "selectByCalling:". The middle one sends a one-argument message to a singe object with the argument ranging over the collection members. * What's the reason for putting a reference to "capacity" in the base Collection protocol? They are not relevant to LinkedList's at all, for instance. (This seems like a leftover from Smalltalk Object's indexed instance vars?) Well, that's a typo -- "capacity" should only be in the protocol. * ' just wondering why you used the name "map:" instead of "collect:" ("collect:" would match with Smalltalk, as do the rest of your select, reject, and detect methods.) Well, I like "map:" better! map is the name nown from enywhere else but Smalltalk. (That is, diverse functional languages) * I notice your Link and LinkList stuff. Does this mean you are doing object creation / destruction each time you do an add or remove to that collection? I know that Smalltalk has Link objects, but do we really want to do this in Objective C? A "LinkList" is a list of objects which respond to "nextLink" (get next link) and "nextLink:" (set next link). Thus a "LinkList" does not do allocation or other management. A "LinkedList" keeps an instance of "IdLink" for each element... ** I think we may have slightly different approaches to this implementation. Perhaps the difference I'm thinking of was shown most clearly when you said, "It is somewhat important that the code is clean and efficient, *as it'll be an example for newcomers.*" [emphasis mine]. I believe we should implement the Collection heirarchy to be as efficient and powerful as possible; and the best implementation may not end up being the perfect example of Objective C *for newcomers*. We can distribute other example programs for that. Ok, we can agree on this -- if we're going to support multi-type collections, the code is going to be ugly anyway, so who cares... Let's just go ahead and hack! /Kresten From mccallum Tue Apr 13 10:50:44 1993 EDT To: Kresten Krab Thorup In-reply-to: <199304122314.AA07462@xiv.iesd.auc.dk> Subject: Re: Collection library Hi Kresten, You write: > My idea is based on NeXT's HashTables. They aren't too ugly, and it > sure would be a pain if you had to use a different class for each key > type (integers, floats, char*'s, etc). > >Ok, I'll look into how to code this. Should we use "Object" suffix >for id'ish selectors and "Element" for all others? This way we'll >have typechecking at least on objects... Yes, I agree and I already have methods with both names in my implementation. >Right -- perhaps we should even have 3 variants "selectByPerforming:", >"selectByPerforming:on:" and "selectByCalling:". The middle one sends >a one-argument message to a singe object with the argument ranging >over the collection members. Yup. These are *exactly* the method names that I now have in my implementation. Well, now our implementationas are sounding very similar, and I wonder if we are loosing the benefit of creating two separate test implementations. Perhaps now we are just being wasteful. I would like to ask what you would think of me taking over the Collection library stuff. * You already have so much to do with the rest of the Objective C implementation, and some people may prefer that other Objective C features such as class variables develop more quickly. * I've given the Collection library a lot of thought; I'm happy to do this for GNU. I will act as a faithful arbiter of ideas from others about the Collection heirarchy---if there is concensus from you and others on implementation ideas with which I disagree, my Collection library will represent the "will of the people." The last thing I want to do it "step on your toes". You have done great work for Objective C, and I have nothing but respect for you. If you feel very strongly about doing the Collection library yourself, I guess there's not much that I can do. Let me know what you think, Best regards, Andrew From krab@iesd.auc.dk Tue Apr 13 11:07:39 1993 X-VM-Attributes: [nil nil nil nil t] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA10412; Tue, 13 Apr 93 11:07:35 -0400 Received: from iesd.auc.dk by cayuga.cs.rochester.edu (5.61/x) id AA05376; Tue, 13 Apr 93 11:07:30 -0400 Received: from xiv.iesd.auc.dk by iesd.auc.dk with SMTP id AA00272 (5.65c8/IDA-1.5/MD for ); Tue, 13 Apr 1993 17:06:36 +0200 Received: by xiv.iesd.auc.dk id AA09966 (5.65c8/IDA-CLIENT/MD); Tue, 13 Apr 1993 17:07:02 +0200 Message-Id: <199304131507.AA09966@xiv.iesd.auc.dk> In-Reply-To: <9304131450.AA06962@vein.cs.rochester.edu> (mccallum@cs.rochester.edu) From: Kresten Krab Thorup To: mccallum@cs.rochester.edu Cc: krab@iesd.auc.dk Subject: Re: Collection library Date: Tue, 13 Apr 1993 17:07:02 +0200 I would like to ask what you would think of me taking over the Collection library stuff. You're most welcome. The reason why I started coding on this was because I thought you said that you wouldn't have time for it? I'd very much like at least an early, but stable, release to be available with gcc 2.4 in a month or so... * You already have so much to do with the rest of the Objective C implementation, and some people may prefer that other Objective C features such as class variables develop more quickly. New features will have to wait until after 2.4. For now, I'll make a pre-release available ASAP and then do fixes and minor enhancements only -- until the next release. I'll be in Moscow next week, so hopefully the pre-release can be out before then. The last thing I want to do it "step on your toes". You have done great work for Objective C, and I have nothing but respect for you. If you feel very strongly about doing the Collection library yourself, I guess there's not much that I can do. I don't feel stronly about doing it -- just having it :-) Please go ahead and code... I can see that you've picked up my libcoll, and you're most welcome to use whatever you like from that. I've not made any noticably changes (at least I don't remember any..) since I put it there. Please keep on informing me, and the list, on what you decide to do. I think it's a good thing that more than one competent programmer has a word to say on the design. Kresten BTW -- Brad Cox sent this to me: Suggestion #1: Stick with the standard interface, such as it is. Described in my book for a few classes. No doubt Ken Lerman could get y Sugestion #2: If you *really*, really can't resist tinkering, consider using the phrase "Member" instead of "Object". Thus aI've always regretted not a dopting the latter convention for collections when I had a chance. But I felt constrained to l convention is perfect and unconstrained perfectionism just causes innocent users problems without improving anything sub-- Brad Cox; bcox@gmu.edu; 703 968 8229 Voice 703 968 8798 Fax George Mason Program on Social and Organizational Learning From mccallum Tue Apr 13 11:50:30 1993 EDT To: Kresten Krab Thorup In-reply-to: <199304131507.AA09966@xiv.iesd.auc.dk> Subject: Re: Collection library Hi Kresten, I accept my mission as Collection heirarchy implementor. I'm thrilled to be able to contribute! I do go through brief periods of busy-ness, but there will not be a problem with me finishing an early stable release of a Collection library for gcc 2.4 in about a month from now. I'll also be happy to periodically send you private releases of the current state of the library. I'll be happy to get the feedback. Re Brad Cox's message: * Do you have a preference for the word "Member" or "Element" in method names? * He says, "Stick with the standard interface as described in his book." I assume by the way you started coding your heirarchy that you don't agree with this. I don't agree either. Some differences are based on the fact his base Cltn class includes an IdArray as an instance variable for holding the contents---yuck. I also prefer some of the NeXT-compatible method names over his: "empty" instead of Cox's "emptyYourself", and "makeObjectsPerform:" instead of Cox's "elementsPerform:". Best regards, Andrew From mccallum Tue Apr 13 19:35:43 1993 EDT To: Kresten Krab Thorup Subject: Object Hi Kresten, Just two little things: * What would you think about adding "-shouldNotImplement:(SEL)aSel" to Object. It's in Smalltalk and it's in NeXT's Object (although it isn't documented). There have been times that I've found it to be useful. * What do you think about the difference between NeXT's "-superclass" and our current "-superClass". If you want to keep "-superClass", we might still want to add "-superclass" for compatibility with NeXT programs? I suppose that their capitalization is more consistent with the way we write "subclass" not "subClass". I sent a subscription message to gcc2-request@cygnus.com. I'm compiling the latest version of gcc right now. I should be able to give you a first glance at my Collection code sometime soon. Cheers, Andrew From mccallum Mon Apr 19 13:45:12 1993 EDT To: Kresten Krab Thorup In-reply-to: <199303091128.AA10780@iesd.auc.dk> Subject: runtime (NOT) - what will it have? Hi Kresten, I should be able to send you a first version of the Collection library this evening. Welcome back to the net. - Andrew Kresten Krab Thorup writes: > Pieter Schoenmakers writes: > > [list of varous classes...] > >I think this is a reasonable beginning of a decent class library. > >At least for me it is :-) > > In my oppinion, an objective C standard library should be in the > spirit of the Smalltalk collection library. As noted, I have a almost > complete library like this (Michael Uhlenberg posted another lately). > If someone is willing to finish/test it he/she can have a copy, but > not for playing around... It is not ready for distribution yet. > > It takes a good programmer to design a such library, but hopefully a > such could be the basis of a lot of other classes, so that they will > have a *consistent* interface. > > /Kresten From mccallum Mon Apr 19 17:03:59 1993 EDT To: Kresten Krab Thorup Subject: Collection library prelim Hi Kresten, My preliminary version of the Collection library can be obtained by anonymous ftp at cs.rochester.edu:pub/libcoll-930419.tar.z It compiles fine, but since I still seem to be having problems getting the results of gcc to run*, I haven't run any tests on it. I'm mostly interested in your comments about functionality and method names anyway. Feel free to send criticism---anything from big picture direction to little name preferences. I'm looking forward to your feedback. * This is getting really frustrating. I grabbed the latest ss-930417.tar.z, configured it for our sparc's, in the Makefile changed prefix and local_prefix to /u/mccallum/usr, and compiled and installed it without problems. But then 'gcc foo.m -lobjc' can't find libobjc.a, and the linker complains about __eprintf missing. When I add the approriate '-L' and a dummy __eprintf, my resulting executables seg fault in the objc runtime. I must be doing something silly. Any suggestions? Andrew -------------------------------------------------------------- R. Andrew McCallum ARPA: mccallum@cs.rochester.edu Computer Science Department UUCP: uunet!cs.rochester.edu!mccallum University of Rochester VOX: (716) 275-2527 Rochester, NY 14627-0226 FEET: CSB Rm. 625 From krab@iesd.auc.dk Tue Apr 27 14:41:28 1993 X-VM-Attributes: [nil nil nil nil t] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA00987; Tue, 27 Apr 93 14:41:25 -0400 Received: from iesd.auc.dk by cayuga.cs.rochester.edu (5.61/x) id AA10847; Tue, 27 Apr 93 14:41:22 -0400 Received: from xiv.iesd.auc.dk by iesd.auc.dk with SMTP id AA06931 (5.65c8/IDA-1.5/MD for ); Tue, 27 Apr 1993 20:39:38 +0200 Received: by xiv.iesd.auc.dk id AA26734 (5.65c8/IDA-CLIENT/MD); Tue, 27 Apr 1993 20:40:24 +0200 Message-Id: <199304271840.AA26734@xiv.iesd.auc.dk> In-Reply-To: <9304271623.AA14573@vein.cs.rochester.edu> "mccallum@cs.rochester.edu" From: Kresten Krab Thorup To: mccallum@cs.rochester.edu Subject: Collection library prelim Date: Tue, 27 Apr 1993 20:40:24 +0200 OK. I'm working on more improvements to the Collection library. I've added preliminary a protocol for collections of objects accessible by index, but not insertable by index (like stacks and queues), and a protocol (subclass of previous) for sorted collections. Sounds fine. My general impression of the collection library is that it's fine. Even though there's still a lot of thing top be coded, the general framework is there. If you have any major, big picture suggested changes, it'd be nice to hear about them before I do a lot more work building on what I've got so far. I suggest we make some typesafe way to keep any kind of type. I think you should make a set of inline functions which manipulate a unioon of all the allowed types. This way we can make perfectly sure that nothing goes wrong. Casting is far from safe, so this would be much better. For special things, such as arrays of things, you could have a dispatch table, keyed by the encoding, which kept accessing functions. In principle: switch (*_desc) { case '*': ((char**)_data)[index] = *((char**)theValue); break; case 's': ((short*data)[index] = *((short*)theValue); break; ... } should be distinct functions all accepting a char* as argument. For speed, this dispatch table could be an array ranging over all char's, which keeps function pointers. Using this, the above is written as: (*(put_val_func[*_desc]))(index, &theValue) Or something like that. Another matter is that you have very few ...Object, and a lot ...Element in the code. I expect that you're planning to do them as well. /Kresten From mccallum Thu Apr 29 19:43:53 1993 EDT To: Kresten Krab Thorup Subject: Collection library again Hi Kresten, Another version of the Objective-C Collection library can be found at cs.rochester.edu:pub/libcoll-930429.tar.z. It still lacks a lot of implementation, and hasn't undergone much testing at all, but there have been a lot of improvements. Here are some of the key issues for your (and others) feedback. Soon I think I'll want to show libcoll to others. Do you have suggestions as to who? It'd be nice to include someone from NeXT. TODO: * Add archiving. * Add sorting capabilities. * Add more classes? * Obviously, fill in relevant "-notImplemented" -------------------------------------------------------------------- Questions: * I've prefixed the names of abstract class with '_'. I thought that making it obvious which classes were abstract might be a good idea (so beginners don't try to create and use them), BUT I could be convinced that using the '_' was a silly idea. Any votes for removing or keeping the underscores? * What should we do with other classes like 'Time'? (which I've also implemented) They don't exactly belong in libcoll. Do we want one big library of basic Objective-C objects, not a separate libcoll? I would like to suggest keeping the runtime and Object implementation separate from all these other classes, though. * I've named the protocol for externally ordered sequential collections "OrdCollecting" (i.e. users can insert elements at arbitrary indeces). Unfortunately, Smalltalk users may get confused because OrderedCollection is means something different for them. Does anyone want to change the name? Any suggestions? * The protocol heirarchy has a nice, clean separation between the sequential collections with internally and externally specified orders. We'd like this to show up in the implementation: i.e. Stack's, Queues, and SortedCollections should not conform to the OrdCollecting protocol (the one that allows insertion at arbitrary indeces). Unfortunately, this causes a little pain in the implementation---for instance the SeqCollection(ForOrdColleting) and _BasicArray/Array stuff. Any complaints or suggestions? * For names like "shallowCopy[Select,Reject,Collect]ByCalling:" I'm happy to take suggestions on a replacement for "shallowCopy" if you can think of something better. * "-species" method needed? * What to return on errors? We need to come up with better error, warning handling in general for Objective C. * Every method that has "Element" in the name also has a duplicate with "Object" in the name (with the types appropriately changed). This seems like a nice feature---help programmer by avoiding a lot of casting, and it gives our collection objects methods names familiar to NeXT programmers. Would anyone prefer that they not be there? * I've implemented LinkedLists based on Link objects. This has the advantage that the user can nicely get at and manipulate the Links, however, it also means there is a fair amount of message passing for east addObject, removeObject, etc. Anyone want to suggest a different implementation? Perhaps something based on an array of structures that includes indeces of the next element. This would prevent us from calling malloc in each insertion. I'm happy to stick with using Link's unless someone want to convince me otherwise. -------------------------------------------------------------------- Changes I'd like in the Objective-C runtime: * Make objc_sizeof_type() public. * Add hash_node_for_key() to hash.h and hash.c. * How about removing cache as a parameter to the hashing functions in hash.h and hash.c. Do the masking on the result of the hash function. This would seem much neater. * Add -shouldNotImplement to Object. -- Andrew -------------------------------------------------------------- R. Andrew McCallum ARPA: mccallum@cs.rochester.edu Computer Science Department UUCP: uunet!cs.rochester.edu!mccallum University of Rochester VOX: (716) 275-2527 Rochester, NY 14627-0226 FEET: CSB Rm. 625 From krab@iesd.auc.dk Thu Apr 29 20:18:18 1993 X-VM-Attributes: [nil nil nil nil t] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA16110; Thu, 29 Apr 93 20:18:14 -0400 Received: from iesd.auc.dk by cayuga.cs.rochester.edu (5.61/x) id AA23431; Thu, 29 Apr 93 20:18:08 -0400 Received: from loke.iesd.auc.dk by iesd.auc.dk with SMTP id AA07035 (5.65c8/IDA-1.5/MD for ); Fri, 30 Apr 1993 02:16:17 +0200 Message-Id: <199304300016.AA07035@iesd.auc.dk> Received: by loke.iesd.auc.dk (4.1/SMI-4.1) id AA26480; Fri, 30 Apr 93 02:17:19 +0200 In-Reply-To: <9304292343.AA28551@vein.cs.rochester.edu> "mccallum@cs.rochester.edu" From: Kresten Krab Thorup To: mccallum@cs.rochester.edu Cc: krab@iesd.auc.dk, burchard@geom.umn.edu.Here.are.some.of.the.key.issues.for.your.feedback.Soon.I.think.I'll.want.to.show.libcoll.to.others.Do.you.have.suggestions.as.to.who.It'd.be.nice.to.include. (and others) Subject: Collection library again Date: Fri, 30 Apr 1993 02:16:17 +0200 Well, why not simply let it out on the gnu-objc list. If you make it clear to people that it's a preliminary release noone will really complain, and you'll have the opportunity to get a larger amount of input. I allowed myself to CC this to Paul. TODO: * Add archiving. Wait a while with this, it's fairly easy to do, and we may redo the archiving stuff if we make up something better. Besides, we've been granted an distributed objects system from WilTel, which also may influence our policy here. * Add more classes? Just do the basic stuf right first. Once these are done it's more easy for other people to se how it should be done, and this make your burden easier :-) * Obviously, fill in relevant "-notImplemented" Fill in with implementations ?? :-) -------------------------------------------------------------------- Questions: * I've prefixed the names of abstract class with '_'. I thought that making it obvious which classes were abstract might be a good idea (so beginners don't try to create and use them), BUT I could be convinced that using the '_' was a silly idea. Any votes for removing or keeping the underscores? I think this is a silly idea. Rather give them long names, which makes them non-user friendly anyway. * What should we do with other classes like 'Time'? (which I've also implemented) They don't exactly belong in libcoll. Do we want one big library of basic Objective-C objects, not a separate libcoll? I would like to suggest keeping the runtime and Object implementation separate from all these other classes, though. By next gcc release (2.4.something) (some time in the furure) we'll put what is now libobjc into libgcc, and use libobjc for the "general" class library. I think we should have one class library which includes all generic classes. For now, we should perhaps keep them seperated into categories like "os-interface" "collection" etc. I've started working on an indexing kit which I'll need for my masters project, so I believe there'll be plenty of classes to put into a general purpose class library -- libobjc. * I've named the protocol for externally ordered sequential collections "OrdCollecting" (i.e. users can insert elements at arbitrary indeces). Unfortunately, Smalltalk users may get confused because OrderedCollection is means something different for them. Does anyone want to change the name? Any suggestions? Why not invent a new name instead, like "IndexedCollection" -- if the library looks like the Smalltalk library, alot of people will get confused if the same name has a radically different meaning. * The protocol heirarchy has a nice, clean separation between the sequential collections with internally and externally specified orders. We'd like this to show up in the implementation: i.e. Stack's, Queues, and SortedCollections should not conform to the OrdCollecting protocol (the one that allows insertion at arbitrary indeces). Unfortunately, this causes a little pain in the implementation---for instance the SeqCollection(ForOrdColleting) and _BasicArray/Array stuff. Any complaints or suggestions? No complaints. Just use "-shouldNotImplement:" and the mis-confomance will turn out at once anyway. This is a dynamic language right? I'll study the hierachies and see if I can make up something better. * For names like "shallowCopy[Select,Reject,Collect]ByCalling:" I'm happy to take suggestions on a replacement for "shallowCopy" if you can think of something better. Here's a suggestion: do the reverse, so that you have a special name for the one that doesn't work on a shallow copy: -selectInPlaceByCalling: -selectByCalling: the [InPlace] doesn't do a copy. This has the effect that whoever uses a `InPlace' version will have to think about it before he does so. Thus making it more safe. * "-species" method needed? Take a look in the Smalltalk code and see where the `^self class' definition in Collection is overridden. This may give you a clue to if it should be there. * What to return on errors? We need to come up with better error, warning handling in general for Objective C. I could easily supply a exception handling mechanism. I think this is a good idea, since it will often simplify a lot of code. * Every method that has "Element" in the name also has a duplicate with "Object" in the name (with the types appropriately changed). This seems like a nice feature---help programmer by avoiding a lot of casting, and it gives our collection objects methods names familiar to NeXT programmers. Would anyone prefer that they not be there? That's fine. Just let'em stay. * I've implemented LinkedLists based on Link objects. This has the advantage that the user can nicely get at and manipulate the Links, however, it also means there is a fair amount of message passing for east addObject, removeObject, etc. Anyone want to suggest a different implementation? Perhaps something based on an array of structures that includes indeces of the next element. This would prevent us from calling malloc in each insertion. I'm happy to stick with using Link's unless someone want to convince me otherwise. Add a kind of LinkedList that keeps objects that already under stand the simple protocol: -nextLink // return next Link -nextLink: // addign next link Plus perhaps accompanying -prevLink messages. It is good to avoid instance variable access, since this makes it far more general (especially in connection with distributed objects) -------------------------------------------------------------------- Changes I'd like in the Objective-C runtime: * Make objc_sizeof_type() public. * Add hash_node_for_key() to hash.h and hash.c. * How about removing cache as a parameter to the hashing functions in hash.h and hash.c. Do the masking on the result of the hash function. This would seem much neater. * Add -shouldNotImplement to Object. I agree on all points. I'll add them right after the gcc 2.3 release. RIght now I'm not allowed to add new features, or change anything that isn't really needed. /Kresten From mccallum Fri Apr 30 11:29:48 1993 EDT To: Kresten Krab Thorup In-reply-to: <199304300016.AA07035@iesd.auc.dk> Subject: Collection library again CC: burchard@geom.umn.edu Kresten Krab Thorup writes: > * The protocol heirarchy has a nice, clean separation between the > sequential collections with internally and externally specified > orders. We'd like this to show up in the implementation: i.e. > Stack's, Queues, and SortedCollections should not conform to the > OrdCollecting protocol (the one that allows insertion at arbitrary > indeces). Unfortunately, this causes a little pain in the > implementation---for instance the SeqCollection(ForOrdColleting) and > _BasicArray/Array stuff. Any complaints or suggestions? > > No complaints. Just use "-shouldNotImplement:" and the mis-confomance > will turn out at once anyway. This is a dynamic language right? I'll > study the hierachies and see if I can make up something better. When I ask [Queue conformsTo:@protocol(OrdCollecting)] I want to get NO. If Queue inherits from Array (which does conform to OrdCollecting), my understanding is that I'll get YES, even if some of the methods in Queue are overridden with "-shouldNotImplement:". Here is a quote from NeXT's Concepts manual: "A class is said to conform to a formal protocol if it adopts the protocol or inherits from a class that adopts it." Hmm,.. I just tested this out with NeXT's cc and with our gcc. Interesting. NeXT's cc does as it says. Our gcc does not. The source for my test program is at the end of this message. NeXT's output: Bar conforms to @protocol Foo 1 Bar2 conforms to @protocol Foo 1 Our gcc's output: Bar conforms to @protocol Foo 1 Bar2 conforms to @protocol Foo 0 I think NeXT's defined behavior makes more sense. Perhaps we should change our gcc. ...and this is why I need BasicArray and Array. It would be nice if the compile-time test for protocol conformance checked the methods defined in superclasses also. > * For names like "shallowCopy[Select,Reject,Collect]ByCalling:" I'm > happy to take suggestions on a replacement for "shallowCopy" if you > can think of something better. > > Here's a suggestion: do the reverse, so that you have a special name > for the one that doesn't work on a shallow copy: > > -selectInPlaceByCalling: > -selectByCalling: > > the [InPlace] doesn't do a copy. This has the effect that whoever uses > a `InPlace' version will have to think about it before he does so. > Thus making it more safe. I agree that it would be nice to have both "copying" and "in place" versions of these operations. And perhaps I could be convinced that the two names you mention are the best ones,... but I'm not convinced yet. I really think we need to make it obvious when reading code which methods return new alloc'ed objects. This is because: (1) Objective-C does not have garbage collection---the programmer has to keep track of new objects and free them when necessary. (2) We teach beginners that the default return value for methods is self. Seeing the results of "-selectByCalling" getting freed does not imply the right thing. > * "-species" method needed? > > Take a look in the Smalltalk code and see where the `^self class' > definition in Collection is overridden. This may give you a clue to > if it should be there. It's overridden in MappedCollection (not in a way we need), Interval, and Symbol. In sum: I won't need it to implement the first base Collection classes, but others may need it later. I'll leave it in. > * What to return on errors? We need to come up with better error, > warning handling in general for Objective C. > > I could easily supply a exception handling mechanism. I think this is > a good idea, since it will often simplify a lot of code. Could you send me this? What I also really need is a mechanism for optionally printing warnings that don't necessarily crash the program. > * I've implemented LinkedLists based on Link objects. This has the > advantage that the user can nicely get at and manipulate the Links, > however, it also means there is a fair amount of message passing for > each addObject, removeObject, etc. Anyone want to suggest a different > implementation? Perhaps something based on an array of structures > that includes indeces of the next element. This would prevent us from > calling malloc in each insertion. I'm happy to stick with using > Link's unless someone want to convince me otherwise. > > Add a kind of LinkedList that keeps objects that already under stand > the simple protocol: > > -nextLink // return next Link > -nextLink: // addign next link > > Plus perhaps accompanying -prevLink messages. When using the LinkedList collection is would be nice to be able to both (1) add arbitrary elements to the collection, just as with all the other collections. (i.e. [llist addElement:"bird"]; or [llist addObject:foo]; where foo is not a Link.) (2) and manipulate the Links themselves. (i.e. [llist2 insertLink:[llist removeLinkAt:1] at:4]; ) My implementation provides this. Needless to say, it can't provide this by insisting on being a collection of objects that conform to the Link protocol. > It is good to avoid > instance variable access, since this makes it far more general > (especially in connection with distributed objects) Hmm... I actually did some (admittedly yucky) direct reading (but not writing) of instance variables in my implementation. Without this the amount of message passing gets really ridiculous. But if we think that people will actually use LinkedList's in which the Link objects are remote (wow!), I suppose I will have to change this. Right now I can't imagine people doing this. What I can imagine is people using a LinkedList whose elements are remote objects. My current implementation handles this nicely. I'm going to go ahead and remove the underscores from the abstract class names, as well as taking some of your other suggestions. Thanks, Andrew --------------- 8< ------------- #include #include @protocol Foo - foo; @end @interface Bar : Object - cow; @end @implementation Bar - cow { printf("cow\n"); } - foo { printf("foo\n"); } @end @interface Bar2 : Bar //- foo; @end @implementation Bar2 /* - foo { return [self notImplemented:_cmd]; } */ @end main() { printf("Bar conforms to @protocol Foo %d\n", (int)[Bar conformsTo:@protocol(Foo)]); printf("Bar2 conforms to @protocol Foo %d\n", (int)[Bar2 conformsTo:@protocol(Foo)]); } --------------- 8< ------------- From burchard@geom.umn.edu Fri Apr 30 00:04:02 1993 X-VM-Attributes: [nil nil nil nil nil] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA16734; Fri, 30 Apr 93 00:03:59 -0400 Received: from cameron.geom.umn.edu by cayuga.cs.rochester.edu (5.61/x) id AA24017; Fri, 30 Apr 93 00:03:56 -0400 Received: from mobius.geom.umn.edu by cameron.geom.umn.edu; Thu, 29 Apr 1993 23:03:54 -0500 Message-Id: <9304300403.AA24769@mobius.geom.umn.edu> Received: by mobius.geom.umn.edu; Thu, 29 Apr 93 23:03:52 -0500 Received: by NeXT.Mailer (1.87.1) Received: by NeXT Mailer (1.87.1) From: burchard@geom.umn.edu To: Kresten Krab Thorup Cc: mccallum@cs.rochester.edu Subject: Re: Collection library again Date: Thu, 29 Apr 93 23:03:52 -0500 I like all of Kresten's comments (especially about not using underscores, and the "InPlace" stuff). And I also encourage you go ahead and post your preliminary design to gnu-objc....I've gotten a lot of really good feedback there. PB From burchard@geom.umn.edu Mon May 3 23:36:01 1993 X-VM-Attributes: [nil nil nil nil t] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA12457; Mon, 3 May 93 23:35:57 -0400 Received: from cameron.geom.umn.edu by cayuga.cs.rochester.edu (5.61/x) id AA08896; Mon, 3 May 93 23:35:54 -0400 Received: from mobius.geom.umn.edu by cameron.geom.umn.edu; Mon, 3 May 1993 22:35:47 -0500 Message-Id: <9305040335.AA00445@mobius.geom.umn.edu> Received: by mobius.geom.umn.edu; Mon, 3 May 93 22:35:52 -0500 Received: by NeXT.Mailer (1.87.1) Received: by NeXT Mailer (1.87.1) From: burchard@geom.umn.edu To: mccallum@cs.rochester.edu Cc: Kresten Krab Thorup Subject: Collections, ownership, and the copy protocol Date: Mon, 3 May 93 22:35:52 -0500 I started looking over libcoll-930429, and the overall design looks good. If the idea of combining all element types in one implementation works out, it would really be quite a relief for the end-user. What I think needs some more thought is ownership of contained objects (which I think we discussed a bit before). There is also apparently some confusion about the purpose of -deepen. An example that begins to expose these issues is the incompatibility of your List class with NeXT's. The latter treats -copy as if it were -shallowCopy. That's because NeXT's List assumes it doesn't own the elements---except during archiving...argggh. Your collection classes also don't yet deal clearly with the ownership issue, which becomes much more important in the absence of garbage collection. If your Lists don't own their elements, what happens when we -copy (now meaning deep copy) one of your Lists and new objects are created at the copy's behest and hidden inside of it? After a few collection manipulations it could be impossible to avoid losing track of memory. The copy protocol is a good place to further dig into these issues. To start with a specific problem, note that -copy already contains -deepen; [copy] is by default equivalent to [[shallowCopy] deepen]. So the following is at least a memory leak: HashTable.m:193 > node->value = [(id)(node->value) copy]; > [(id)(node->value) deepen]; Part of reason for -deepen was to avoid direct access to another object's ivars in -copy. However, you are still using this practice in -shallowCopy itself, because even shallow copies (in your interpretation) have to be deepened a bit. Given your semantics, you can do this more cleanly by making the base class [shallowCopy] be [[super shallowCopy] fillShallow], and then overriding only -fillShallow in subclasses. However, the way I probably would have organized this is to keep -shallowCopy as the raw runtime operation (similar to -alloc). In addition to copying the array of element pointers, -deepen would copy only those elements in the array which the collection owns. In this way, the end-user method, -copy, would be appropriately deep or shallow, depending on element ownership. I'm not sure it makes sense to have an explicit choice of shallow and deep copies, because this seems to simply be an indirect way of telling the collection whether the objects are "internal" or "external" to the collection. Well, maybe we should just go ahead and tell the collection about this ownership issue directly, especially since the collection needs to know this for all sorts of operations other than copying (-free, -read:, -write:, remote messaging, etc). This doesn't have to burden the user much since the overwhelming majority of the time, collections are used to group and manage "external" objects. The "external" case can be the default, which requires no special intervention by the user. What are your thoughts on these issues? -------------------------------------------------------------------- Paul Burchard ``I'm still learning how to count backwards from infinity...'' -------------------------------------------------------------------- From mccallum Fri May 7 13:44:50 1993 EDT To: burchard@geom.umn.edu In-reply-to: <9305070108.AA01882@mobius.geom.umn.edu> Subject: Re: Collections, ownership, and the copy protocol Cc: Kresten Krab Thorup Hi Paul, You've convinced me of the benefit of -deepen, but I haven't quite understood some of your other points. burchard@geom.umn.edu writes: > > * Shallow copying: We should make it *impossible* to end > > up with a collection that contains only a copy of the ivars > > (i.e. I don't think I should not leave "-shallowCopy" as > > it is). The users can royally screw themselves with this behavior. > > The point of these methods is to provide a consistent protocol for > extending the end-user copying method, -copy. Just as you extend > +new by overriding -init, you extend -copy by overriding -deepen. Yup, I agree. I see the similarities between "new/alloc/init" and "copy/shallowCopy/deepen". > Such a protocol is beneficial because both +new and -copy are sent to > objects other than the one which must eventually initialize itself. > Both -init and -deepen exist in order to eliminate the need---and > temptation---to directly access another object's ivars (as you do in > libcoll). Which ivar access are you referring to here? Something related to copying, or are you talking about Link objects? Is this a suggestion to use @protocol's for links instead of the current setup? > I'd favor having a single -copy method and letting the collection > object keep track of which objects are external and internal. That's > just one vote, of course---let the gnu-objc crowd in on these issues. OK, I'd like the make sure I understand how the ownership semantics might work. Is this what you have in mind?: Add "-setOwner:(BOOL)flag" and "-(BOOL)owner" to the protocol. Using an instance variable, a collection object keeps track of whether or not it owns all its contents. If a collection is the owner, then: 1) it sends "-free" to its content objects when the collection is free'd, 2) it writes the object (instead of writeReference) when the collection is written, 3) it sends an effective [[ shallowCopy] deepen] to each of the contents when responding to "-copy". Any time we keep track of ownership, I don't understand how we will avoid the all-too-easily-reachable situation in which two different collection objects think they own the same object (resulting in errors when the collections are free'd). fooObject = [[Foo alloc] init]; coll1 = [[[Array alloc] init] setOwner:YES]; coll2 = [[[Array alloc] init] setOwner:YES]; [coll1 addObject:fooObject]; [coll2 addObject:fooObject]; It seems that what we really need here is reference counting. I could add a reference counting protocol to the collections, but there would still be easy, natural ways of getting around it. ** What we really need is real garbage collection. ** But I don't think we're going to get it, and I'm not sure we would really want it's overhead. There is an important difference between "new/alloc/init" and "copy/shallowCopy/deepen". With "new" there is no ambiguity about what the programmer wants. With "copy" it is possible that the programmer could want two different things: 1) a deep copy completely independent of the original, 2) a new collection of pointers to the old objects. There is nothing inherent in the original collection itself that would indicate which of these options that programmer wanted---the choice depends on the situation, what the programmer intends to do with the resulting copy. ' looking forward to your feedback, Andrew From mccallum Fri May 7 16:18:44 1993 EDT To: burchard@geom.umn.edu CC: Kresten Krab Thorup In-reply-to: <9305071933.AA02648@mobius.geom.umn.edu> Subject: Re: Collections, ownership, and the copy protocol burchard@geom.umn.edu writes: > I would love to see an *optional* garbage collector in libobjc. > > But I think GC should be optional for libcoll, because most of the > time, collection objects will be used as lightweight ways to organize > external objects. This most important task should not be hindered by > the "threat" of GC. Ditto. - Andrew P.S. I'm thinking about merging the two sequenceable collection protocols into one. (i.e. not distinguishing between the protocol that lets you access and remove objects by index, and the protocol that does the above and also lets you insert objects at arbitrary indices.) It's a meaningful distinction, but it's starting to look like it's not worth the mess it causes. This means that objects conforming to SortedCollecting would have to override insertObject:at:, etc, with "-shouldNotImplement". (It would be nice to set up some automatic way for objects to respond properly to "-respondsTo:" for these methods.) Opinions on the merge? I'm also thinking about modifying the method names in a bit, and making my inherit from , in essence recognizing that IndexedCollection's are also keyed---by unsigned integers. This scheme makes things like a MappedCollection ala Smalltalk particularly clean. Opinions? P.P.S. I'm off for the weekend. Talk to you all again on Monday. From burchard@geom.umn.edu Fri May 7 11:21:59 1993 X-VM-Attributes: [nil nil nil nil t] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA01701; Fri, 7 May 93 11:21:55 -0400 Received: from cameron.geom.umn.edu by cayuga.cs.rochester.edu (5.61/x) id AA25566; Fri, 7 May 93 11:24:01 -0400 Received: from mobius.geom.umn.edu by cameron.geom.umn.edu; Thu, 6 May 1993 20:08:05 -0500 Message-Id: <9305070108.AA01882@mobius.geom.umn.edu> Received: by mobius.geom.umn.edu; Thu, 6 May 93 20:08:04 -0500 Received: by NeXT.Mailer (1.87.1) Received: by NeXT Mailer (1.87.1) From: burchard@geom.umn.edu To: mccallum@cs.rochester.edu Cc: Kresten Krab Thorup Subject: Re: Collections, ownership, and the copy protocol Date: Thu, 6 May 93 20:08:04 -0500 > * Shallow copying: We should make it *impossible* to end > up with a collection that contains only a copy of the ivars > (i.e. I don't think I should not leave "-shallowCopy" as > it is). The users can royally screw themselves with this behavior. The point of these methods is to provide a consistent protocol for extending the end-user copying method, -copy. Just as you extend +new by overriding -init, you extend -copy by overriding -deepen. Such a protocol is beneficial because both +new and -copy are sent to objects other than the one which must eventually initialize itself. Both -init and -deepen exist in order to eliminate the need---and temptation---to directly access another object's ivars (as you do in libcoll). I'd favor having a single -copy method and letting the collection object keep track of which objects are external and internal. That's just one vote, of course---let the gnu-objc crowd in on these issues. PB From mccallum Wed May 19 16:38:20 1993 EDT To: Kresten Krab Thorup Subject: libcoll almost ready for first public showing Hi Kresten, I've been working away on some significant improvements to libcoll, and soon I'd like to announce it in gnu-objc. In order to keep everything together I'd like to make it available at your ftp site (iesd.auc.dk). Will that be OK? Do I have permission to put things there now? Just to fill you in on some of the biggest changes: * got rid of OrderedCollecting / SequencedCollecting distinction, which was bogus anyway. Using your suggestion, I called the protocol for ordered collections "IndexedCollecting" * I added a "KeyedCollecting" protocol that recognizes the similarities between all collections containing elements accessible by a key. * I completely rewrote the LinkedList implementation. Removed the instance variable access, defined a protocol and created a LinkList class, as you did in your preliminary libcoll. * ..and of course, many bug fixes * (I haven't dealt with archiving or ownership issues yet). -- Andrew P.S. When can I get your OO stream implementation? Will it have a "printOn:" convention also? From krab@iesd.auc.dk Wed May 19 18:49:36 1993 X-VM-Attributes: [nil nil nil nil t] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA23313; Wed, 19 May 93 18:49:33 -0400 Received: from iesd.auc.dk by cayuga.cs.rochester.edu (5.61/x) id AA21995; Wed, 19 May 93 18:49:31 -0400 Received: from xiv.iesd.auc.dk by iesd.auc.dk with SMTP id AA28299 (5.65c8/IDA-1.5/MD for ); Thu, 20 May 1993 00:49:13 +0200 Received: by xiv.iesd.auc.dk id AA14316 (5.65c8/IDA-CLIENT/MD); Thu, 20 May 1993 00:49:21 +0200 Message-Id: <199305192249.AA14316@xiv.iesd.auc.dk> In-Reply-To: <9305192038.AA28474@vein.cs.rochester.edu> "mccallum@cs.rochester.edu" From: Kresten Krab Thorup To: mccallum@cs.rochester.edu Cc: krab@iesd.auc.dk Subject: libcoll almost ready for first public showing Date: Thu, 20 May 1993 00:49:21 +0200 I've been working away on some significant improvements to libcoll, and soon I'd like to announce it in gnu-objc. I'm absolutely excited! Can I have a copy and just look around? In order to keep everything together I'd like to make it available at your ftp site (iesd.auc.dk). Will that be OK? Do I have permission to put things there now? Sure. I'll setup an accountfor you when I get to the office first thing tomorrow morning. * got rid of OrderedCollecting / SequencedCollecting distinction, which was bogus anyway. Using your suggestion, I called the protocol for ordered collections "IndexedCollecting" Fine. * I added a "KeyedCollecting" protocol that recognizes the similarities between all collections containing elements accessible by a key. I'm looking forward to se how you handle all these different kinds of arguments... * I completely rewrote the LinkedList implementation. Removed the instance variable access, defined a protocol and created a LinkList class, as you did in your preliminary libcoll. This is really the old time/space tradeoff. Would you like "link" objects hanging around or not. In my first implementation I had both, perhaps that would be worth considering. * (I haven't dealt with archiving or ownership issues yet). P.S. When can I get your OO stream implementation? Will it have a "printOn:" convention also? As of now I've not done anything fancy at low level streams. I've made various things around streams, such as the Binary{Encoder,Decoder} (Together implementing the encoding level of typed streams) classes whose instances are connected to something conforming to (providing writeBytes and readBytes). Besides this I've made some INET/Socket classes. I've not gone very far, most of it is rather primitive right now. I think the design of the streams library should be based on a cooperation between to kinds of "streams": Stream providers and Stream filters. Thus, I'll not have a "FileStream" on which you can do a "printf", but seperate formatters and providers. The encoders are examples of filters. My current plans look like this (*==implemented): UnixStream * anything that has a file descriptor FileStream * a seekable named file PipeStream * unixish piped streams (non-seekable) SocketStream * streamed (tcp/SOCK_STREAM) sockets INETSocket * sockets connected to ports on hosts (AF_INET) UNIXSocket - UNIX domain sockets (AF_UNIX) NamedPipe - UNIX named pipes UnnamedPipe - things that come from socketpair() MemoryStream - in-memory bytestream MemoryFile - looks like a file MemoryPipe - byte oriented pipe, manages indep. read/write pointers StreamFilter * has initializers for common Streams like files TypedStream * guess what! AsciiFiler - Same as TypedStream StdFilter - printf, scanf etc... Since filters will often have distinct input and output streams "below" these are kept in distinct ivars even though they may be equal. All of the streams are only "bytestreams". Filters are more like interpreters or small "compilers" which perform transformations. Please let me know if you have any comments, extensions, questions regarding this. Until july 1st I'll be *very* buzy doing my exams, so I'll not be able to do anything but discussions until then. /Kresten BTW: My University has just offered me 10h/week payed for doing FSF/GNU stuff (~$15/h). Sure I'll accept (I'm doing it anyway) but isn't it just great? This should be considered a contribution to FSF since we cannot transfer funds directly. From mccallum Thu May 20 11:49:03 1993 EDT To: Kresten Krab Thorup In-reply-to: <199305192249.AA14316@xiv.iesd.auc.dk> CC: Paul Burchard Subject: Re: libcoll almost ready for first public showing Hi Kresten, You said you wanted to have an early peek at libcoll... Take a look at cs.rochester.edu:pub/libcoll-930520.tar.z. Beginning by looking at the README is a better idea than it was before since it's a little more coherent now. Could I also get an early peek at your Stream library? Enjoy, Andrew From krab@iesd.auc.dk Thu May 20 17:20:36 1993 X-VM-Attributes: [nil nil nil nil t] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA28366; Thu, 20 May 93 17:20:33 -0400 Received: from iesd.auc.dk by cayuga.cs.rochester.edu (5.61/x) id AA26452; Thu, 20 May 93 17:20:30 -0400 Received: from xiv.iesd.auc.dk by iesd.auc.dk with SMTP id AA10233 (5.65c8/IDA-1.5/MD for ); Thu, 20 May 1993 23:18:01 +0200 Received: by xiv.iesd.auc.dk id AA22999 (5.65c8/IDA-CLIENT/MD); Thu, 20 May 1993 23:18:10 +0200 Message-Id: <199305202118.AA22999@xiv.iesd.auc.dk> From: Kresten Krab Thorup To: mccallum@cs.rochester.edu Cc: krab@iesd.auc.dk, burchard@geom.umn.edu Subject: Collection of comments :-) Date: Thu, 20 May 1993 23:18:10 +0200 In general it look absolutely fabulous! I have some random comments from just reading the source. Any method that causes elements to be removed from a collection should return that element if possible. This is generally so, but Delegate does not conform to this. How about letting ElementListLink not inherit object, but then delegate to the content object? Since we have this implicit cast to elt, all ..Object methods are implemented as wrappers for ..Element methods. This wil not encurage anyone to use those since it costs an extra method call :-) I think it should be ok to have nil objects in collections. The missing element and non-exsisting indiced should be ~0 i.e. one with all bits set. This is much less likely to cause conflict than 0. `withElements...:whileTrue: ' is a great invention. Encurage people to use this instead of nasty goto hacks that may cause trouble for internal cleanup. Implement a generic qsort, which takes an array-accesor function (elem*(*)(void* array, int index) as extra argument. Using this you can use the same qsort for all kinds of indexed collections. printForDebugger may be obviated by a special DebuggerStreamFilter allowing the debugger to use `encodeTo:' or the like... Did you try the exception handling? It will not make it even to 2.4.1, but I think I'll distribute an extended runtime shortly so you shouldnt care if it's not in right now. I have to decide on the +initialize stuff. Please convince me to something! Neat that you use OBJC_FREE/OBJC_MALLOC this allows for alternative mechanisms to be installed (such as gc). I'll put them in the runtime headerfiles and use them when I get time. Please remind me or send me a patch.... Why not add: OBJC_CMALLOC -- cleaes content. OBJC_AMALLOC allocate memory that will not contain pointers `atomic' for future gc! -[Dictionary addObject] may do something reasonable if the argument conforms to the protocol :-) i.e. answering to -key and -value etc. KeyedCollection's should decide how to handle -makeElementsPerform and friends. I think it should simply iterate on the values. If -conformsTo: is gonna be heavily used, I could make the runtime keep a real hash table in stead of the current linear table. Someone build a preprocessor allowing one to "inherit" documentation for methods! Set: Should intersectWith:, unionWith:, differenceWith: not come in shallowCopy versions as well? Why not make Stack a subclass of ordinary Arrays? Why use CircularArray, which has more overhead? Why does the system depend on the assertion in +[Collection initialize]? The hashing needs an update. You're welcome to send me patches. It is absolutely GREAT! Congratulations! /Kresten From krab@iesd.auc.dk Thu May 20 17:34:46 1993 X-VM-Attributes: [nil nil nil nil t] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA28473; Thu, 20 May 93 17:34:43 -0400 Received: from iesd.auc.dk by cayuga.cs.rochester.edu (5.61/x) id AA26555; Thu, 20 May 93 17:34:42 -0400 Received: from xiv.iesd.auc.dk by iesd.auc.dk with SMTP id AA10404 (5.65c8/IDA-1.5/MD for ); Thu, 20 May 1993 23:34:22 +0200 Received: by xiv.iesd.auc.dk id AA23084 (5.65c8/IDA-CLIENT/MD); Thu, 20 May 1993 23:34:31 +0200 Message-Id: <199305202134.AA23084@xiv.iesd.auc.dk> In-Reply-To: <199305202118.AA22999@xiv.iesd.auc.dk> "krab@iesd.auc.dk" From: Kresten Krab Thorup To: mccallum@cs.rochester.edu Cc: krab@iesd.auc.dk, burchard@geom.umn.edu Subject: Filenames and other names Date: Thu, 20 May 1993 23:34:31 +0200 Filenames should be reduced to 14 chars. I suggest `Collection' is shortened to `Cltn' -- but only for file names. Some time in the future, RMS will allow me to put what is now `libobjc.a' into `libgcc.a'. This will release libobjc.a to contain stuff like the collectio stuff here and my streams plus other generic stuff. For now, we should perhaps make up a good name for this library, perhaps `libobjective.a' that's 14 chars... /Kresten Talking of filenames: Smalltalk has a neat subclass of string for filenames. This one contains generic path name manipulation, so that this may be hidden if used on another OS. From mccallum Fri May 21 11:39:03 1993 EDT To: Kresten Krab Thorup CC: burchard@geom.umn.edu In-reply-to: <199305202118.AA22999@xiv.iesd.auc.dk> Subject: Collection of comments :-) Hello, friends, Kresten Krab Thorup writes: > In general it look absolutely fabulous! I have some random comments > from just reading the source. Good! I'm glad you like it. > Any method that causes elements to be removed from a collection should > return that element if possible. This is generally so, but Delegate > does not conform to this. I assume you mean DelegateList? I just changed -delegateListRemoveObject to return the object. Is this what you mean? > How about letting ElementListLink not inherit object, but then > delegate to the content object? Interesting idea. So then ElementListLink wouldn't inherit from ListLink (because I think that ListLink should inherit from Object, don't you?). This is fine. What should we do if the contents of the LinkedList are not Object's, though? Perhaps we should have both ElementListLink and ObjectListLink, and I could implement ObjectListLink with your suggestion. Tell me if you think this is a good idea, and I'll do it. > Since we have this implicit cast to elt, all ..Object methods are > implemented as wrappers for ..Element methods. This wil not encurage > anyone to use those since it costs an extra method call :-) Yeah, I know... sigh. So I figure that the programmers who care will go through the extra trouble to use the ...Element calls, and everyone else will have pretty method names. Do you have any other solutions? Reimplementing all the ..Object methods not only seems like a major pain, but also does nasty things to inheritance and overriding. > I think it should be ok to have nil objects in collections. The > missing element and non-exsisting indiced should be ~0 i.e. one with > all bits set. This is much less likely to cause conflict than 0. OK, I can do this. What is the best way to get ~0? Using 0xffffffff doesn't seem very portable. Is UINT_MAX what we want; will it do the right thing on 64-bit machines? > `withElements...:whileTrue: ' is a great invention. Encurage people > to use this instead of nasty goto hacks that may cause trouble for > internal cleanup. Yup, I rather like it myself also. > Implement a generic qsort, which takes an array-accesor function > (elem*(*)(void* array, int index) as extra argument. Using this you > can use the same qsort for all kinds of indexed collections. I agree that implementing qsort for use will all Array-based IndexedCollection's is a good idea? Buy why use this array-accessor function---why not [.. elementAtIndex:] ? > printForDebugger may be obviated by a special DebuggerStreamFilter > allowing the debugger to use `encodeTo:' or the like... Good, this is just what I want. For now, I've already generalized printForDebugger to correctly print all different kinds of contents: int's, float's, SEL's, etc. > Did you try the exception handling? It will not make it even to > 2.4.1, but I think I'll distribute an extended runtime shortly so you > shouldnt care if it's not in right now. Well, I'm not sure calling EX_RAISE() when an index is out of bounds is what the user would what? What do you think? > I have to decide on the +initialize stuff. Please convince me to > something! I agree strongly with Paul Burchard. ** Keep the NeXT semantics. ** > Neat that you use OBJC_FREE/OBJC_MALLOC this allows for alternative > mechanisms to be installed (such as gc). I'll put them in the runtime > headerfiles and use them when I get time. Please remind me or send me > a patch.... Why not add: OBJC_CMALLOC -- cleaes content. OBJC_AMALLOC > allocate memory that will not contain pointers `atomic' for future gc! Yup, in fact the new definitions of OBJC_MALLOC, etc. dereference a function pointer, so switching to GC should be a breeze. This is not something that is particular to libcoll, you should take a look at it and decide if you want to do it a different way or not. > -[Dictionary addObject] may do something reasonable if the argument > conforms to the protocol :-) i.e. answering to -key and > -value etc. I could pull the -key and -value from an object and insert them into the Dictionary, but the Dictionary would not keep the object itself. We might get in trouble if the user expected the Dictionary to keep track of the original object. I'm really not sure what to do here. For now I'll nothing, but I'm open to more suggestions, or just convincing that this above behavior is fine. > KeyedCollection's should decide how to handle -makeElementsPerform and > friends. I think it should simply iterate on the values. They already do, just by inheritance. In KeyedCollections -withElementsCall: passes all the "values" to the function. > If -conformsTo: is gonna be heavily used, I could make the runtime > keep a real hash table in stead of the current linear table. My feeling on this is, "wait and see" if -conformsTo: turns out to be a performance bottleneck. > Someone build a preprocessor allowing one to "inherit" documentation > for methods! I would be nice to come up with a machine extractable format for putting documentation in the source code. > Set: Should intersectWith:, unionWith:, differenceWith: not come in > shallowCopy versions as well? OK, I can add those. > Why not make Stack a subclass of ordinary Arrays? Why use > CircularArray, which has more overhead? You're absolutely right. CircularArray makes sense for Queue's, but not Stacks. I'll change it. > Why does the system depend on the assertion in +[Collection initialize]? sizeof(elt) must == sizeof(void*) because the compare and hash functions used by hash.c take void* arguments, and the entire elt needs to get into the compare and hash functions. I'm a bit uncomfortable with these casts. What if we rewrote hash.c to use elt's! I bit scary,.. but it certainly would make libcoll's implementation cleaner. Hmm, I'm trying to remember why I thought it was so important that sizeof(id) == sizeof(elt)... I guess sizeof(id) will always == sizeof(void*) anyway, n'est-ce pas? > The hashing needs an update. You're welcome to send me patches. Let me know what you think we should do about the idea above (re. elt data type used in libcoll and void* used in hash.c). > It is absolutely GREAT! Congratulations! It feels good to get positive feedback. I'm glad you like it. ' looking forward to your reponse on this note. - Andrew From mccallum Fri May 21 11:44:47 1993 EDT To: Kresten Krab Thorup CC: burchard@geom.umn.edu In-reply-to: <199305202134.AA23084@xiv.iesd.auc.dk> Subject: Filenames and other names Kresten Krab Thorup writes: > Filenames should be reduced to 14 chars. I suggest `Collection' is > shortened to `Cltn' -- but only for file names. Oh *Yuck*! I dislike the idea of changing the classnames to use "Cltn", but I *really* dislike the idea of having filenames different from class names. ....I can't get over how disgusting I think it is that we have to keep filenames to 14 chars. ...do we really have to? :-( > Talking of filenames: Smalltalk has a neat subclass of string for > filenames. This one contains generic path name manipulation, so that > this may be hidden if used on another OS. I'm not sure I understand. Are you saying there may be a way for me to keep my nice, unabreviated class names? -- Andrew From mccallum Fri May 21 11:52:22 1993 EDT To: Kresten Krab Thorup In-reply-to: <199305211257.AA18951@iesd.auc.dk> Subject: shallowCopyReplaceFrom:to:with: Hello again, Kresten Krab Thorup writes: > Here is an implementation that works for all `IndexedCollection's I think the current implementation of shallowCopyReplaceFrom:to:with: in IndexedCollection also works for all IndexedCollection's, BUT I do notice that your implementation does have different semantics. To me, the phrase "replace from x to y with" implies that the space vacated by the elements from x to y would be filled with all the elements of replaceCollection, even if replaceCollection were smaller or larger than the gap from x to y. How about adding this method with the name shallowCopyReplaceFrom:to:using: which suggests to me the semantics of your implementation. I'm open to your suggestions on this. > - shallowCopyReplaceFrom: (unsigned)start to: (unsigned)stop > with: (id )replaceCollection > { > id newColl = [self shallowCopy]; > unsigned index = start; > BOOL continue = YES; > void doIt (elt e) > { > [newColl replaceElementAtIndex: index with: e]; > continue = (index++ != stop); > } > [replaceCollection withElementsCall: doIt whileTrue: &continue]; > return newColl; > } -- Andrew From mccallum Fri May 21 11:53:57 1993 EDT To: Kresten Krab Thorup In-reply-to: <199305211438.AA20257@iesd.auc.dk> Subject: GapArray + Storage implemented Great! Thank you! I've already put them in with the others. Andrew From krab@iesd.auc.dk Fri May 21 11:04:11 1993 X-VM-Attributes: [nil nil nil nil t] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA01680; Fri, 21 May 93 11:04:09 -0400 Received: from iesd.auc.dk by cayuga.cs.rochester.edu (5.61/x) id AA29329; Fri, 21 May 93 11:04:08 -0400 Received: from loke.iesd.auc.dk by iesd.auc.dk with SMTP id AA20508 (5.65c8/IDA-1.5/MD for ); Fri, 21 May 1993 17:03:46 +0200 Message-Id: <199305211503.AA20508@iesd.auc.dk> Received: by loke.iesd.auc.dk (4.1/SMI-4.1) id AA17500; Fri, 21 May 93 17:04:13 +0200 From: Kresten Krab Thorup To: mccallum@cs.rochester.edu Cc: krab@iesd.auc.dk Subject: Portability hints Date: Fri, 21 May 1993 17:03:46 +0200 This is just a bunch of hint on hwo to make your code more portable. Don't include any system header files if it can be avoided. Even stdlib.h is not available on all systems. sizeof(long) == sizeof(int) should not be relied upon. On most 64 bits machines, int is 32 bit and long is 64. Use `0' instead of NULL. 0 is a valid pointer of any kind, and you mey get trouble from headerfiles if you need NULL. GNU style: Use (*fptr)(args) syntax when calling a function via a pointer. This is part of the GNU coding standards, and besides it makes it more explicit that it actually is a function pointer. From mccallum Fri May 21 11:55:17 1993 EDT To: Kresten Krab Thorup In-reply-to: <199305211503.AA20508@iesd.auc.dk> Subject: Portability hints Thanks, for the good suggestions. I agree with all of them. I'll make the appropriate changes. - Andrew From mccallum Fri May 21 13:00:50 1993 EDT To: Kresten Krab Thorup CC: burchard@geom.umn.edu Subject: String classes We should think about the possibility of a String class that conforms to . I think it could work... I'm not sure I'm up to volunteering to do it right now, though. We should also take a look at NeXT's String heirarchy. I've got *.h files that I distilled from poking around the NeXT's library. I could give them to anyone who is interested. Eventually we're going to want to duplicate NeXT's @"a new constant string object" functionality in GNU Objective-C. ...Hmmm, I wonder if NeXT would donate their String classes :-) -- Andrew From krab@iesd.auc.dk Fri May 21 14:56:56 1993 X-VM-Attributes: [nil nil nil nil nil] Status: RO Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA02962; Fri, 21 May 93 14:56:53 -0400 Received: from iesd.auc.dk by cayuga.cs.rochester.edu (5.61/x) id AA00554; Fri, 21 May 93 14:56:52 -0400 Received: from loke.iesd.auc.dk by iesd.auc.dk with SMTP id AA22831 (5.65c8/IDA-1.5/MD for ); Fri, 21 May 1993 20:56:28 +0200 Message-Id: <199305211856.AA22831@iesd.auc.dk> Received: by loke.iesd.auc.dk (4.1/SMI-4.1) id AA18695; Fri, 21 May 93 20:56:56 +0200 In-Reply-To: <9305211552.AA07771@vein.cs.rochester.edu> "mccallum@cs.rochester.edu" From: Kresten Krab Thorup To: mccallum@cs.rochester.edu Cc: krab@iesd.auc.dk Subject: shallowCopyReplaceFrom:to:with: Date: Fri, 21 May 1993 20:56:28 +0200 To me, the phrase "replace from x to y with" implies that the space vacated by the elements from x to y would be filled with all the elements of replaceCollection, even if replaceCollection were smaller or larger than the gap from x to y. I just realize that what you describe is the semanthics of `splice' in perl. An excerpt from the online docs: splice(ARRAY,OFFSET,LENGTH,LIST) splice(ARRAY,OFFSET,LENGTH) splice(ARRAY,OFFSET) Removes the elements designated by OFFSET and LENGTH from an array, and replaces them with the elements of LIST, if any. Returns the elements removed from the array. The array grows or shrinks as necessary. If LENGTH is omitted, removes everything from OFFSET onward. Why not use this semanthics, which is very close to what you suggested. Forget about what I suggested in my last letter. /Kresten From krab@iesd.auc.dk Fri May 21 15:00:52 1993 Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA03015; Fri, 21 May 93 15:00:49 -0400 Received: from iesd.auc.dk by cayuga.cs.rochester.edu (5.61/x) id AA00574; Fri, 21 May 93 15:00:48 -0400 Received: from loke.iesd.auc.dk by iesd.auc.dk with SMTP id AA22867 (5.65c8/IDA-1.5/MD for ); Fri, 21 May 1993 21:00:25 +0200 Message-Id: <199305211900.AA22867@iesd.auc.dk> Received: by loke.iesd.auc.dk (4.1/SMI-4.1) id AA18715; Fri, 21 May 93 21:00:52 +0200 In-Reply-To: <9305211544.AA07693@vein.cs.rochester.edu> "mccallum@cs.rochester.edu" From: Kresten Krab Thorup To: mccallum@cs.rochester.edu Cc: burchard@geom.umn.edu Cc: krab@iesd.auc.dk Subject: Filenames and other names Date: Fri, 21 May 1993 21:00:25 +0200 Kresten Krab Thorup writes: > Filenames should be reduced to 14 chars. I suggest `Collection' is > shortened to `Cltn' -- but only for file names. Oh *Yuck*! I dislike the idea of changing the classnames to use "Cltn", but I *really* dislike the idea of having filenames different from class names. ....I can't get over how disgusting I think it is that we have to keep filenames to 14 chars. ...do we really have to? :-( It is not because I like it, but I really think so. Consider it as a standard you'll have to swallow -- it will make the life so much easier for a lot of people. One could argue that the class names should be the same as file names, but I don't like the idea of abbreviating the class names either. /Kresten From krab@iesd.auc.dk Fri May 21 15:28:45 1993 Received: from cayuga.cs.rochester.edu by sol.cs.rochester.edu (5.61/x) id AA03233; Fri, 21 May 93 15:28:42 -0400 Received: from iesd.auc.dk by cayuga.cs.rochester.edu (5.61/x) id AA00724; Fri, 21 May 93 15:28:38 -0400 Received: from loke.iesd.auc.dk by iesd.auc.dk with SMTP id AA23141 (5.65c8/IDA-1.5/MD for ); Fri, 21 May 1993 21:28:14 +0200 Message-Id: <199305211928.AA23141@iesd.auc.dk> Received: by loke.iesd.auc.dk (4.1/SMI-4.1) id AA18862; Fri, 21 May 93 21:28:42 +0200 In-Reply-To: <9305211539.AA07630@vein.cs.rochester.edu> "mccallum@cs.rochester.edu" From: Kresten Krab Thorup To: mccallum@cs.rochester.edu Cc: burchard@geom.umn.edu Subject: Collection of comments :-) Date: Fri, 21 May 1993 21:28:14 +0200 > Any method that causes elements to be removed from a collection should > return that element if possible. This is generally so, but Delegate > does not conform to this. I assume you mean DelegateList? I just changed -delegateListRemoveObject to return the object. Is this what you mean? Yup. > How about letting ElementListLink not inherit object, but then > delegate to the content object? Interesting idea. So then ElementListLink wouldn't inherit from ListLink (because I think that ListLink should inherit from Object, don't you?). This is fine. What should we do if the contents of the LinkedList are not Object's, though? Perhaps we should have both ElementListLink and ObjectListLink, and I could implement ObjectListLink with your suggestion. Tell me if you think this is a good idea, and I'll do it. What you describe sounds fine. > Since we have this implicit cast to elt, all ..Object methods are > implemented as wrappers for ..Element methods. This wil not encurage > anyone to use those since it costs an extra method call :-) Yeah, I know... sigh. So I figure that the programmers who care will go through the extra trouble to use the ...Element calls, and everyone else will have pretty method names. Do you have any other solutions? Reimplementing all the ..Object methods not only seems like a major pain, but also does nasty things to inheritance and overriding. You're right. It was only an observation. > I think it should be ok to have nil objects in collections. The > missing element and non-exsisting indiced should be ~0 i.e. one with > all bits set. This is much less likely to cause conflict than 0. OK, I can do this. What is the best way to get ~0? Using 0xffffffff doesn't seem very portable. Is UINT_MAX what we want; will it do the right thing on 64-bit machines? I believe ~0L is the best way to do it. Since it only has to be computed once you could make a special global instance of elt which is properly initialized... > Implement a generic qsort, which takes an array-accesor function > (elem*(*)(void* array, int index) as extra argument. Using this you > can use the same qsort for all kinds of indexed collections. I agree that implementing qsort for use will all Array-based IndexedCollection's is a good idea? Buy why use this array-accessor function---why not [.. elementAtIndex:] ? Yes, why not simply implement quicksort as a method of IndexedCollection. He'res an implementation from the Sather library somewhere to make life easier for you. quicksortL(l:INT;r:INT) is -- quicksort the array from start to finish i:INT := l; j:INT := r; x:INT; w:INT; x := sortlist[(l + r) / 2 ]; loop until sortlist[i] >= x loop i := i + 1; end; until x >= sortlist[j] loop j := j - 1; end; if i <= j then w := sortlist[i]; sortlist[i] := sortlist[j]; sortlist[j] := w; i := i + 1; j := j - 1; end; if i > j then break; end; end; if l < j then quicksortL(l,j); end; if i < r then quicksortL(i,r); end; end; -- quicksortL > Did you try the exception handling? It will not make it even to > 2.4.1, but I think I'll distribute an extended runtime shortly so you > shouldnt care if it's not in right now. Well, I'm not sure calling EX_RAISE() when an index is out of bounds is what the user would what? What do you think? Index out of bounds is a fine condition for an exception. > I have to decide on the +initialize stuff. Please convince me to > something! I agree strongly with Paul Burchard. ** Keep the NeXT semantics. ** Ok, I'll change it as soon as 2.4.1 is released. I will see if rms accepts the change now. > -[Dictionary addObject] may do something reasonable if the argument > conforms to the protocol :-) i.e. answering to -key and > -value etc. I could pull the -key and -value from an object and insert them into the Dictionary, but the Dictionary would not keep the object itself. We might get in trouble if the user expected the Dictionary to keep track of the original object. I'm really not sure what to do here. For now I'll nothing, but I'm open to more suggestions, or just convincing that this above behavior is fine. If objects have the constraint thet they're `isEqual:' if their keys are `isEqual:' then it should be ok I believe. However, who'd ever use objects anyway -- they belong in a garbage collected language. > Why does the system depend on the assertion in +[Collection initialize]? sizeof(elt) must == sizeof(void*) because the compare and hash functions used by hash.c take void* arguments, and the entire elt needs to get into the compare and hash functions. I'm a bit uncomfortable with these casts. What if we rewrote hash.c to use elt's! I bit scary,.. but it certainly would make libcoll's implementation cleaner. The hash table should be recoded since it doesn't scale very well for large tables. I did one dynamic scalable hashtable a while back in C++, which could possibly be used. In any case, I think the hash table should use elt's... Hmm, I'm trying to remember why I thought it was so important that sizeof(id) == sizeof(elt)... I guess sizeof(id) will always == sizeof(void*) anyway, n'est-ce pas? Right. > The hashing needs an update. You're welcome to send me patches. Let me know what you think we should do about the idea above (re. elt data type used in libcoll and void* used in hash.c). I think it's fine. Having realized this union matter there is no other option! /Kresten