   This file documents the features and implementation of The GNU
Objective-C collection class library.

   Copyright (C) 1993 Free Software Foundation, Inc.

   Permission is granted to make and distribute verbatim copies of this
manual provided the copyright notice and this permission notice are
preserved on all copies.

   Permission is granted to copy and distribute modified versions of
this manual under the conditions for verbatim copying, provided also
that the section entitled "GNU Library General Public License" is
included exactly as in the original, and provided that the entire
resulting derived work is distributed under the terms of a permission
notice identical to this one.

   Permission is granted to copy and distribute translations of this
manual into another language, under the above conditions for modified
versions, except that the section entitled "GNU Library General Public
License" and this permission notice may be included in translations
approved by the Free Software Foundation instead of in the original
English.

Libcoll
*******

   This manual documents how to install and use the GNU Objective-C
Collection class library (or `libcoll'), version 931026, for use with
`gcc' version 2.5.0.

   It is nothing but a skeleton now, mostly containing rough notes.  In
the future it will be fleshed out and the text will be polished.

Contributors to GNU Objective-C Collection library
**************************************************

   * Andrew McCallum <mccallum@cs.rochester.edu> designed the protocol
     and class heirarchies, and wrote the otherwise unattributed
     classes.

   * Kresten Krab Thorup <Kresten_Thorup@NeXT.COM> made libcoll
     possible by writing the GNU Objective-C runtime.  He also
     contributed the GapArray and Storage classes.

   * Paul Kunz <Paul_Kunz@slac.stanford.edu> did a lot to fix the List
     class.

   * Kresten Krab Thorup <krab@iesd.auc.dk>, Paul Burchard
     <burchard@geom.umn.edu>, Paul Kunz <Paul_Kunz@slac.stanford.edu>,
     Geoffery Knauth <gsk@marble.com>, Steve Naroff <snaroff@next.com>,
     Richard Stallman <rms@gnu.ai.mit.edu> and others contributed to
     discussions about the library.

Installing GNU Objective-C Collection library
*********************************************

  1. Type `./configure' to configure the Makefile for your system.

  2. Type `make' to make the library.

  3. Type `make install' to install the library.

  4. Try testing... if you like.

   See `INSTALL' for more detailed instruction.

   <<This section unfinished.>>

Trouble in Installation
***********************

   Try to fix the problem.  Send patches to mccallum@cs.rochester.edu.

   <<This section incomplete>>

Overview
********

   The GNU Objective-C collection class library is a library of
Objective-C objects with similar functionality to Smalltalk's
Collection objects.  It includes the classes: Set, Bag, Array,
CircularArray, GapArray, Queue, Stack, Heap, LinkedList, BinaryTree,
SplayTree, RBTree, Dictionary, MappedCollector, EltNodeCollector and
DelegateList.

   Outside of its main heirarchy it also includes List, HashTable and
Storage objects compatible with NeXT's objects of the same name.

   This release also includes a very preliminary version of a String
object.  I threw it together mostly as a thought-experiment to make
sure that my changes to the IndexedCollection abstract superclass would
fit well with a String class.  Many methods are left unimplemented; it
is not useable.

   As an extra plus, the library includes classes Magnitude and Time.
Eventually the .h files for these will be moved outside of the "coll"
directory.

Organization
************

   The library is built around several protocols:

   * The <Collecting> protocol is root of the collection protocol
     heirarchy.  The <Collecting> protocol defines the most general
     interface to a collection of elements.  Elements can be added,
     removed, and replaced.  The contents can be tested, enumerated,
     and enumerated through various filters.  Elements may be objects,
     or any C type included in the "elt" union given in elt.h, but all
     elements of a collection must be of the same C type.  [NOTE: for
     examples see Set and Bag.]

   * The <KeyedCollecting> protocol inherits from the <Collecting>
     protocol.  The <KeyedCollecting> protocol defines the interface to
     a collection of elements that are accessible by a key, where the
     key is some unique element.  Pairs of (key element, content
     element) may be added, removed and replaced.  The keys and
     contents may be tested, enumerated, and copied.  [NOTE: for
     examples see Dictionary and MappedCollector.]

   * The <IndexedCollecting> protocol inherits from the
     <KeyedCollecting> protocol.  The <IndexedCollecting> protocol
     defines the interface to a collection of elements that are
     accessible by a key that is an index, where the indeces in a
     collection are a contiguous series of unsigned integers beginning
     at 0.  This is the root of the protocol heirarchy for all
     collections that hold their elements in some order.  Elements may
     be accessed, inserted, replaced and removed by their index.
     [NOTE: for examples see Array and LinkedList.]

   * The <LinkedListComprising> protocol defines the interface to an
     object that may be an element in a LinkedList.  LinkedList is a
     collection object based on a doubly linked list.  [NOTE: for an
     example see LinkedListNode.]

   * The <BinaryTreeComprising> protocol defines the interface to an
     object that may be an element in a BinaryTree.  BinaryTree is a
     collection object based on a binary trees.  [NOTE: for an example
     see BinaryTreeNode.]

   Here is the object inheritance heirarchy.  All collection abtract
superclasses (classes which are not usable without subclassing) end
with "Collection"; all protocols end with "ing"; all collection
protocols end with "Collecting".

        Collection <Collecting>
            Set
                Bag
            KeyedCollection <KeyedCollecting>
                Dictionary
                MappedCollector
                IndexedCollection <IndexedCollecting>
                    Array
                        Stack
                        GapArray
                        CircularArray
                            Queue
                        Heap
                    LinkedList
                    BinaryTree
                    RBTree
                    EltNodeCollector
                    String
         DelegateList

         HashTable
         List
         Storage

   <<This section unfinished.>>

Stylistic Conventions and Design Philosophy
*******************************************

Stylistic Conventions
=====================

   * Objective-C source files have file extension `.m'. Both
     C-compatibility header files and class declaration files have
     extension `.h'.

   * Objective-C class names begin with capital letters.  Multi-word
     class names capitalize each word, with no underscore separation.

   * Include files that define Objective-C classes begin with capital
     letters (as do the names of the classes themselves).

   * All protocols end with "ing".  All collection protocols end with
     "Collecting".  All collection abtract superclasses (classes which
     are not usable without subclassing) end with "Collection";

   * Include files that supply function prototypes for other C
     functions are all lower case.

   * Instance variables begin with an underscore, are all lower case,
     and have underscores separating their component words.  The leading
     underscore distinguishes them from varibles defined inside methods.

   * All include files define a preprocessor variable __X_h_INCLUDE_GNU,
     where X is the name of the file, and conditionally compile only if
     this has not been already defined.

The design philosophy.
======================

   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 make the Collection method names a little more descriptive, while
     keeping them close to Smalltalk.  (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 since so much of the
     functionality overlaps, I have merged them, and it doesn't
     actually look all that bad.

   * Objective C doesn't have Smalltalk Blocks.

     Passing pointers to functions is a reasonable substitute.  This is
     made easier with gcc's nested functions and the LAMBDA() macro
     defined in coll/collstd.h.

   * Smalltalk does automatic garbage collection; Objective C doesn't.

     I think it should be made obvious which methods allocate a new
     object.  Hence "-shallowCopyAs:[Bag class]" instead of "as:[Bag
     class]".

   * We have usable Collection classes (Set, Bag, Array, etc) with
     functionality matching Smalltalk's objects, but there are good
     reasons for not having the abstract superclass structure match
     Smalltalk exactly.

   <<This section unfinished.>>

Content types
*************

   Collections can hold either objects or primitive C types.  More
specifically, collections can hold any of the types in the `elt' union
defined in `coll/elt.h'.  All contents of a collection must be of the
same type.

   You declare which type the collection will hold at collection
initialization time, and the type can not be changed later.  You
specify the type using the Objective-C `@encode()' directive.  You can
find out the type held by a collection with the method
`contentEncoding' (see Querying.).

   Many operations are independent of the type the collection holds.
For example the method `-(unsigned)count' returns the number of members
in the collection.

   Other operations need to take arguments of different types depending
on whether the contents are objects or some other type.  In this case
there will be two methods, distinguished by the words `Object' and
`Element' in their method name.  For example, `-removeObject:anObject'
vs `-(elt)removeElement:(elt)anElement'.

   <<Unfinished.>>

Creating a Collection
*********************

Basic Creating
==============

 - Method on Collection:  -init

 - Method on Collection:  -initEncoding: (const char *)CONTENTENCODING

   Create with `alloc' and `init'.  Specify the type of contents using
`initEncoding:'.  For example:

     id arrayHoldingInts = [[Array alloc] initEncoding:@encode(int)];

   <<This section unfinished.>>

Keyed Creating
==============

Freeing a Collection or its Elements
************************************

   You can free all the objects in a collection and empty it using
`freeObjects'.  You can emtpy a collection without freeing the contents
using `empty'.  You can free a collection without freeing the contents
using `free'.

   <<This section unfinished.>>

Adding Elements to a Collection
*******************************

   Talk about adding.

Basic Adding
============

   Adding, adding if absent, adding a copy, adding all contents of
another collection, adding contents if absent, adding with varargs.

 - Method on Collection:  -addObject: NEWOBJECT
 - Method on Collection:  -addElement: (elt)NEWELEMENT
     Adds NEWOBJECT to the receiving collection.  Returns self.

 - Method on Collection:  -addObjectIfAbsent: NEWOBJECT
 - Method on Collection:  -addElementIfAbsent: (elt)NEWELEMENT
     Adds NEWOBJECT to the receiving collection only if NEWOBJECT isn't
     there already.  Returns self.

 - Method on Collection:  -addContentsOf: (id <Collecting>)NEWOBJECT
     Adds all the elements in ACOLLECTION to the receiving collection.
     Returns self.

 - Method on Collection:  -addContentsOfIfAbsent: (id
          <Collecting>)NEWOBJECT
     <<Undocumented>>  Returns self.

 - Method on Collection:  -addObjectsCount: (unsigned)COUNT, ...
 - Method on Collection:  -addElementsCount: (unsigned)COUNT, ...
     <<Undocumented>>  Returns self.

     Here is an example
          id o1 = [[Foo alloc] init];
          id o2 = [[Bar alloc] init];
          id myArray = [[[Array alloc] init] addObjectsCount: 2, o1, o2];

Keyed Adding
============

   If the collection's contents are accessible by a key, members can be
inserted at a specified key.  See KeyedCollecting protocol.

 - Method on KeyedCollection:  -insertObject: NEWCONTENTOBJECT atKey:
          (elt)AKEY
 - Method on KeyedCollection:  -insertElement: (elt)NEWCONTENTELEMENT
          atKey: (elt)AKEY
     <<Undocumented>>  returns self.

Indexed Adding
==============

   Furthermore, if the collections contents are accessible by an index
(an unsigned integer key), members can be appended, prepended.  Inserted
members push other members down to make room.  See IndexedCollecting
protocol.

 - Method on IndexedCollection:  -insertObject: NEWOBJECT atIndex:
          (unsigned)INDEX
 - Method on IndexedCollecting:  -insertElement: (elt)NEWELEMENT
          atIndex: (unsigned)INDEX
     <<Undocumented>>  returns self.

 - Method on IndexedCollection:  -insertObject: NEWOBJECT before:
          OLDOBJECT
 - Method on IndexedCollecting:  -insertElement: (elt)NEWELEMENT
          before: OLDOBJECT
     <<Undocumented>>  returns self.

 - Method on IndexedCollection:  -insertObject: NEWOBJECT after:
          OLDOBJECT
 - Method on IndexedCollecting:  -insertElement: (elt)NEWELEMENT after:
          OLDOBJECT
     <<Undocumented>>  returns self.

 - Method on IndexedCollection:  insertContentsOf: (id
          <Collecting>)ACOLLECTION atIndex: (unsigned)INDEX
     <<Undocumented>>  returns self.

 - Method on IndexedCollection:  -appendObject: NEWOBJECT
 - Method on IndexedCollecting:  -appendElement: (elt)NEWELEMENT
 - Method on IndexedCollection:  -prependObject: NEWOBJECT
 - Method on IndexedCollecting:  -prependElement: (elt)NEWELEMENT
     <<Undocumented>>  returns self.

 - Method on IndexedCollection:  -appendContentsOf: (id
          <Collecting>)ACOLLECTION
 - Method on IndexedCollection:  -prependContentsOf: (id
          <Collecting>)ACOLLECTION
     <<Undocumented>>  returns self.

   <<This section unfinished.>>

Removing Elements from a Collection
***********************************

   About removing...

   <<This section unfinished.>>

Replacing Elements in a Collection
**********************************

   <<This section unfinished.>>

Enumerating the Contents of a Collection
****************************************

   Enumeration methods allow you to perform a specified operation on the
members of a collection.  You can operate on all the members, operate on
all the members until a flag is set, operate only on the members that
pass some test, or operate on the results of passing the members through
a modifying function.  Each of the enumerators come in pairs: one method
for enumerating in place, and another method that is "safe" for
enumerating when the operation changes the contents of the receiving
collection.  If the contents of the collection are changed during the
enumeration you must use the "safe" methods.

Safe vs Unsafe Enumerating
==========================

   The simple enumerators operate on the collection in-place.  If the
contents of the collection change during the enumeration, you must use
the "safe" version of the enumerator instead.

   It works by making a shallow copy of the receiver, performing the
enumeration using the shallow copy, then freeing the shallow copy.

   All enumerators have both "safe" and plain versions.

   <<This section unfinished.>>

Basic Enumerating
=================

   The most basic enumerator is

 - Method on Collection:  -withObjectsCall: (void(*)(id))FUNC
 - Method on Collection:  -safeWithObjectsCall: (void(*)(id))FUNC
 - Method on Collection:  -withElementsCall: (void(*)(elt))FUNC
 - Method on Collection:  -safeWithElementsCall: (void(*)(elt))FUNC
     Calls the function FUNC with each the members of the collection.
     Returns self.

 - Method on Collection: (BOOL) -getNextObject: (id *)ANOBJECTPTR
          withEnumState: (void**)ENUMSTATE
 - Method on Collection: (BOOL) -getNextElement: (elt *)ANELEMENTPTR
          withEnumState: (void**)ENUMSTATE

 - Method on Collection:  -withElementsCall: (void(*)(elt))AFUNC
          whileTrue: (BOOL*)FLAG
 - Method on Collection:  -safeWithElementsCall: (void(*)(elt))AFUNC
          whileTrue: (BOOL*)FLAG

Keyed Enumerating
=================

Indexed Enumerating
===================

 - Method on IndexedCollection: (BOOL) -getPrevObject: (id *)
          ANOBJECTPTR withEnumState: (void**)ENUMSTATE
 - Method on IndexedCollection: (BOOL) -getPrevElement: (elt *)
          ANELEMENTPTR withEnumState: (void**)ENUMSTATE

 - Method on IndexedCollection:  -withObjectsInReverseCall:
          (void(*)(id))AFUNC
 - Method on IndexedCollection:  -safeWithObjectsInReverseCall:
          (void(*)(id))AFUNC
 - Method on IndexedCollection:  -withElementsInReverseCall:
          (void(*)(elt))AFUNC
 - Method on IndexedCollection:  -safeWithElementsInReverseCall:
          (void(*)(elt))AFUNC

 - Method on IndexedCollection:  -withObjectsInReverseCall:
          (void(*)(id)) AFUNC whileTrue: (BOOL *)FLAG
 - Method on IndexedCollection:  -safeWithObjectsInReverseCall:
          (void(*)(id)) AFUNC whileTrue: (BOOL *)FLAG
 - Method on IndexedCollection:  -withElementsInReverseCall:
          (void(*)(elt)) AFUNC whileTrue: (BOOL *)FLAG
 - Method on IndexedCollection:  -safeWithElementsInReverseCall:
          (void(*)(elt)) AFUNC whileTrue: (BOOL *)FLAG

 - Method on IndexedCollection:  -makeObjectsPerformInReverse: (SEL)
          ASEL
 - Method on IndexedCollection:  -safeMakeObjectsPerformInReverse:
          (SEL) ASEL
 - Method on IndexedCollection:  -makeObjectsPerformInReverse: (SEL)
          ASEL with: ARGOBJECT
 - Method on IndexedCollection:  -safeMakeObjectsPerformInReverse:
          (SEL) ASEL with: ARGOBJECT

Defining Functions In Place with LAMBDA()
=========================================

   There may not already be a function that does the operation you want
performed during an enumeration.  In this case you will have to write
such a function yourself.

   If the function will be used more than once, you should write it as C
functions are usually defined.  However, if the function will only be
used for this one enumeration and the function is small, using the
`LAMBDA' macro may be easier and more clear.

 - Macro: LAMBDA(RETTYPE, ARGS, BODY)
     `LAMBDA' is a macro for defining a nested function and returning a
     pointer to that function.  You can use `LAMBDA' wherever a
     function pointer is required.  RETTYPE is the C type returned by
     the function.  ARGS is the parenthesis-enclosed list of arguments
     to the function.  (Declare them just like in an ANSI function
     definition.)  BODY is the curly-bracket-enclosed body of the
     function.

     For example, you could create a pointer to a function that adds its
     arguments like this:
          LAMBDA(int, (int a, int b), {return a + b;})

   `LAMBDA' is particularly convenient for enumeration methods because
the macro can be placed in the position of the method argument.  For
instance, you can write:
       - fooMethod
       {
         id newColl;
         ...
         newColl = [self emptyCopyAs:[Array class]];
         [self withObjectsCall:
               LAMBDA(void, (id o), {[newColl addObject:[o copy]];})];
         return self;
       }
   instead of writing:
       - fooMethod
       {
         id newColl = [self emptyCopyAs:[Array class]];
         void myTmpFunc(id o)
           {
             [newColl addObject:[o copy]];
           }
         ...
         [self withObjectsCall:myTmpFunc];
         return self;
       }
   In these examples, there may be many lines of code between the
declarations at the top of the method and the `withObjectsCall:' at the
bottom of the method.  Using `LAMBDA' allows you to declare the
function where it is used, instead of arbitrarily far from where it is
used.

   The name `LAMBDA' comes from lambda calculus and LISP.

   The `LAMBDA' macro and some similar macros are defined in
`coll/collstd.h'.

Filtered Enumerating
====================

Enumerating with Keyed Collections
==================================

Enumerating with Indexed Collections
====================================

   <<This section unfinished.>>

Duplicating
***********

   Talk about shallow and deep copies.

   <<This section unfinished.>>

Archiving
*********

   You can write collections to a stream.  You can read them back in
again.  Talk about the `-awake' method.

 - Method on Collection:  -write: (TypedStream*)ASTREAM
     <<Undocumented>>  Returns self.

 - Method on Collection:  -read: (TypedStream*)ASTREAM
     <<Undocumented>>  Returns self.

   <<This section unfinished.>>

Querying
********

   <<This section unfinished.>>

Basic Querying
==============

 - Method on Collection: (BOOL) -isEmpty
     Returns YES if the receiver contains no members; returns NO
     otherwise.

 - Method on Collection: (const char *) -contentEncoding
     Returns a description of the C type that the receiving collection
     can hold.  The description is a string of the form returned by the
     Objective-C `@encode' directive.

Keyed Querying
==============

Indexed Querying
================

Sorting
*******

   <<This section unfinished.>>

Choosing the Right Class
************************

   Talk about keys or no keys, ordered or not ordered.  Talk about the
classes the require protocol-conforming objects as members.

   <<This section unfinished.>>

Set
===

   <<This section unfinished.>>

Bag
===

   A Bag is ...

 - Method on Bag:  -addObject: NEWOBJECT withOccurrences:
          (unsigned)COUNT
 - Method on Bag:  -addElement: (elt)NEWELEMENT withOccurrences:
          (unsigned)COUNT

 - Method on Bag:  -removeObject: OLDOBJECT occurrences: (unsigned)COUNT
 - Method on Bag:  -removeElement: (elt)OLDELEMENT occurrences:
          (unsigned)COUNT

   <<This section unfinished.>>

Dictionary
==========

   A Dictionary is ...

MappedCollector
===============

   A MappedCollector is ...

Array
=====

   An Array is ...

Array Methods
=============

 - Method on Array: (unsigned) +defaultCapacity

 - Method on Array: (unsigned) +defaultGrowFactor

 - Method on Array:  -initEncoding: (const char *)
     CONTENTENCODING capacity: (unsigned) ACAPACITY

 - Method on Array:  -setCapacity: (unsigned) NEWCAPACITY

 - Method on Array:  -setGrowFactor: (unsigned) ANUM

Stack
=====

 - Method on Stack:  -pushObject: NEWOBJECT
 - Method on Stack:  -pushElement: (elt)NEWELEMENT

 - Method on Stack:  -popObject: NEWOBJECT
 - Method on Stack:  -popElement: (elt)NEWELEMENT

 - Method on Stack:  -topObject
 - Method on Stack: (elt) -topElement

 - Method on Stack:  -exchangeTop

   A Collection is ...

KeyedCollection
===============

IndexedCollection
=================

To Do List and Questions
************************

   I would greatly appreciate your feedback on the questions below.
Please email your thoughts to mccallum@cs.rochester.edu.

To Do
=====

   * Fix tonnes of bugs. (Metric because they are bigger, as are my
     bugs, I'm sure.)

   * finish RBTree, especially -removeElement:  Finish SplayTree.

   * Address the quesions in the next section below.

   * Test the inclusion of double's in the elt union.

   * Write a good hash function for floats and doubles.  This from
     libg++.texi: `unsigned int foldhash(double x);' a hash function
     for doubles that exclusive-or's the first and second words of x,
     returning the result as an integer.

   * Many implementations could be made more efficient.  Libcoll hasn't
     been efficiency tuned at all.  Overridding some methods in certain
     classes could make things more efficient (especially
     EltNodeCollector).

   * Fix all the subclassResponsibility comments in *.h

   * Add more classes?

   * Redo archiving (waiting for Stream objects from Kresten).  Consider
     ownership issues.  If content object conforms to
     <ReferenceCounting> protocol, do the right thing.  Support a good
     "-printOn:" convention, ala Smalltalk.

   * Write more programs for testing libcoll; clean up testing.  The
     programs should verify their own results.

   * Fix installation procedure (I just put it in, and it's my first
     time using autoconf.  I'm libel to have done some silly things.
     Also I need to change the treatment of tests dir.  Also, some
     places in the source that need to check config information don't.)

   * Fix the treatment of float in HashTable.m

   * I will finish libcoll documentation.

Questions
=========

   * The -getNextElement:enumState: scheme for enumerating has terrible
     potential for misuse leading to memory leaks.  Currently several
     classes will induce memory leaks if the programmer stops the
     enumeration before all elements have been 'gotten'.  I'm open to
     ideas for alternative implementations.

   * Does anyone really miss the ability to set the comparison function
     independent of the element encoding?  If it's really important we
     can come up with ways to do this and still be able to archive
     comparison functions.

   * Should we keep the -safe... enumeration methods?  They sure do add
     a lot of clutter to the protocols.  If we got rid of them people
     would have to alloc an Array, copy the contents, and free the Array
     themselves.

   * What would people think about removing the ...Object methods, and
     just having the ...Element methods instead?  It might be a bit
     more difficult to use, but it would reduce clutter significantly.
     The ...Element methods are more efficient to use anyway, since
     most ...Object methods are wrappers around ...Element calls.  I'm
     not sure what I think we should do.

   * Perhaps we should put more safety checks into LinkedList,
     BinaryTree, etc:  Check that node is not already part of another
     collection (by checking that neighbor pointers are nil?)  In method
     "insertObject:newObject after:oldObject" make sure that oldObject
     is a member of self.  ...It seems that there is a lot of potential
     for nasty bugs with mistakes like these.

   * What about "Function Names::      Printable strings which are the
     name of the current function."  This is a menu item in gcc.info-6.
     Could this make a difference to archiving comparison functions?
     Where are the details on this?

   * HashTable.m (-initKeyDesc:valueDesc:capacity:)  I tried to make it
     portable, but I didn't try very hard.  Did I do it right?

   * I fixed -emptyCopy in all the subclasses, but the -emptyCopy scheme
     seems pretty fagile.  How about calling -initFoo: inside
     -emptyCopy?  This way we avoid having yet another method in which
     instance vars must be initialized to some consistent state.
     -allocCopy would never even get called.  <<ObjC insiders: This is
     a less well-expressed version of what we've just been discussing
     in email.>>

   * The situation with LinkedListNode and LinkedListEltNode, (and the
     analagous classes for BinaryTree's and RBTree's) are just crying
     out for multiple inheritance.  Anyone have ideas that are prettier
     than my quick fix using #include ?

   * Somes classes, like RBTree, depend on a certain ordering of
     elements to maintain internal consistency.  How should we define
     the behavior of methods whose names imply that the user can set
     the ordering of elements independent of these constraints? (like
     -appendElement: or -insertElement:atIndex: for instance).  I see
     three possibilities:
       1. The methods do what they say.  Give the user the power to
          override the default ordering.

       2. The methods do not do what they say, but call addElement:
          instead.  This lets the class maintain its internal
          consistency, but it has the potential to be a bit confusing
          to the user.

       3. The methods trigger a -shouldNotImplement: error.  This
          solution perhaps best expresses the reality of the situation,
          but it's a bit strange for a class to signal an error on a
          method which is in a protocol the class conforms to.
            Currently I'm using solution #1 (in most classes?).

   * I created libcoll.texi by copying libg++.texi.  Some of the text
     is taken verbatim.  Is this a problem?

   * If you don't like the organization of the documentation and you
     have suggestions for changes, please say so now, not after it's
     all been written.

   * Something like this needed?  - elementDidChange: (elt*)elementPtr;
     Currently you have to remove, change, add, for some classes.

Questions leftover from last release
====================================

   * Opinions on the error reporting scheme?  See also tests/test5.m.

   * NeXT prefixes all their names with "NX" to prevent name conflicts.
     Should GNU be doing something similar?  I'd rather use a cleaner
     solution.  (This has been discussed in email.)

   * Should I include _comparison_function as an instance variable of
     Collection?  Putting it back in could make some things more
     efficient, but several classes don't have configurable
     comparisonFunction's (i.e. String, LinkedList, BinaryTree,
     RBTree), so they don't need it.

   * In the current implementation of BinaryTree (and RBTree and
     SplayTree) the -addElement: method puts the element in sorted
     order, HOWEVER, the user has the capability of putting elements in
     unsorted order by sending -insertElement:before:
     -insertElement:after: or -insertElement:atIndex:.  Should I make
     these three methods call -addElement: instead?  The methods
     wouldn't do what their names implied, but it would ensure sorted
     order was preserved.

   * I've been told that GNU filenames should be 14 chars or less.  I
     don't want to abbreviate my classnames, but I think using .h
     @interface files with names different than the class name is even
     worse.  ** I want to keep my unabbreviated filenames!! **  What to
     do, what to do... I can't believe that *all* GNU classnames will be
     limited to 12 characters forever and ever--disgusting.

Changes I'd like in the Objective-C runtime and gcc:
====================================================

   (See collstd.[hm].)

   * Make OBJC_MALLOC() and friends public.  Have the runtime and
     Object.m use them.  See collstd.[hm].

   * Give hash.[hc] functionality more like collhash.[hc], i.e.: Add
     hash_node_for_key() to hash.h and hash.c.  Change hash_next() so
     that more than one enumeration of the contents can happen
     concurrently.  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.

How to contribute
=================

   Programmers who have written Objective-C classes that they believe
to be of general interest are encouraged to write to
mccallum@cs.rochester.edu.  Contributing code is not difficult. Here are
some general guidelines:

   * FSF must maintain the right to accept or reject potential
     contributions.  Generally, the only reasons for rejecting
     contributions are cases where they duplicate existing or
     nearly-released code, contain unremovable specific machine
     dependencies, or are somehow incompatible with the rest of the
     library.

   * Acceptance of contributions means that the code is accepted for
     adaptation into libg++.  FSF must reserve the right to make
     various editorial changes in code. Very often, this merely entails
     formatting, maintenance of various conventions, etc. Contributors
     are always given authorship credit and shown the final version for
     approval.

   * Contributors must assign their copyright to FSF via a form sent out
     upon acceptance. Assigning copyright to FSF ensures that the code
     may be freely distributed.

   * Assistance in providing documentation, test files, and debugging
     support is strongly encouraged.

   Extensions, comments, and suggested modifications of existing libcoll
features are also very welcome.

Protocol Index
**************

Class Index
***********