     START-INFO-DIR-ENTRY
     * Libcoll::                      The objc collection class library.
     END-INFO-DIR-ENTRY

     [file version.texi not included]

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 LIBCOLL_VERSION, for use with gcc version GCC_VERSION.

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
************************

     [file TODO.texi not included]

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.