Introduction to container class prototypes
******************************************

   As a temporary mechanism enabling the support of generic classes,
the GNU C++ Library distribution contains a directory (`g++-include')
of files designed to serve as the basis for generating container
classes of specified elements.  These files can be used to generate
`.h' and `.cc' files in the current directory via a supplied shell
script program that performs simple textual substitution to create
specific classes.

   While these classes are generated independently, and thus share no
code, it is possible to create versions that do share code among
subclasses. For example, using `typedef void* ent', and then generating
a `entList' class, other derived classes could be created using the
`void*' coercion method described in Stroustrup, pp204-210.

   This very simple class-generation facility is useful enough to serve
current purposes, but will be replaced with a more coherent mechanism
for handling C++ generics in a way that minimally disrupts current
usage.  Without knowing exactly when or how parametric classes might be
added to the C++ language, provision of this simplest possible
mechanism, textual substitution, appears to be the safest strategy,
although it does require certain redundancies and awkward constructions.

   Specific classes may be generated via the `genclass' shell script
program. This program has arguments specifying the kinds of base
types(s) to be used. Specifying base types requires two arguments. The
first is the name of the base type, which may be any named type, like
`int' or `String'. Only named types are supported; things like `int*'
are not accepted. However, pointers like this may be used by supplying
the appropriate typedefs (e.g., editing the resulting files to include
`typedef int* intp;'). The type name must be followed by one of the
words `val' or `ref', to indicate whether the base elements should be
passed to functions by-value or by-reference.

   You can specify basic container classes using `genclass base
[val,ref] proto', where `proto' is the name of the class being
generated.  Container classes like dictionaries and maps that require
two types may be specified via `genclass -2 keytype [val, ref],
basetype [val, ref] proto', where the key type is specified first and
the contents type second.  The resulting classnames and filenames are
generated by prepending the specified type names to the prototype names,
and separating the filename parts with dots.  For example, `genclass
int val List' generates class `intList' residing in files `int.List.h'
and `int.List.cc'. `genclass -2 String ref int val VHMap' generates
(the awkward, but unavoidable) class name `StringintVHMap'. Of course,
programmers may use `typedef' or simple editing to create more
appropriate names.  The existence of dot seperators in file names
allows the use of GNU make to help automate configuration and
recompilation. An example Makefile exploiting such capabilities may be
found in the `libg++/proto-kit' directory.

   The `genclass' utility operates via simple text substitution using
`sed'. All occurrences of the pseudo-types `<T>' and `<C>' (if there
are two types) are replaced with the indicated type, and occurrences of
`<T&>' and `<C&>' are replaced by just the types, if `val' is
specified, or types followed by "&" if `ref' is specified.

   Programmers will frequently need to edit the `.h' file in order to
insert additional `#include' directives or other modifications.  A
simple utility, `prepend-header' to prepend other `.h' files to
generated files is provided in the distribution.

   One dubious virtue of the prototyping mechanism is that, because
sources files, not archived library classes, are generated, it is
relatively simple for programmers to modify container classes in the
common case where slight variations of standard container classes are
required.

   It is often a good idea for programmers to archive (via `ar')
generated classes into `.a' files so that only those class functions
actually used in a given application will be loaded.  The test
subdirectory of the distribution shows an example of this.

   Because of `#pragma interface' directives, the `.cc' files should be
compiled with `-O' or `-DUSE_LIBGXX_INLINES' enabled.

   Many container classes require specifications over and above the base
class type. For example, classes that maintain some kind of ordering of
elements require specification of a comparison function upon which to
base the ordering.  This is accomplished via a prototype file `defs.hP'
that contains macros for these functions. While these macros default to
perform reasonable actions, they can and should be changed in
particular cases. Most prototypes require only one or a few of these.
No harm is done if unused macros are defined to perform nonsensical
actions. The macros are:

`DEFAULT_INITIAL_CAPACITY'
     The initial capacity for containers (e.g., hash tables) that
     require an initial capacity argument for constructors.  Default:
     100

`<T>EQ(a, b)'
     return true if a is considered equal to b for the purposes of
     locating, etc., an element in a container.  Default: (a == b)

`<T>LE(a, b)'
     return true if a is less than or equal to b Default: (a <= b)

`<T>CMP(a, b)'
     return an integer < 0 if a<b, 0 if a==b, or > 0 if a>b.  Default:
     (a <= b)? (a==b)? 0 : -1 : 1

`<T>HASH(a)'
     return an unsigned integer representing the hash of a.  Default:
     hash(a) ; where extern unsigned int hash(<T&>).  (note: several
     useful hash functions are declared in builtin.h and defined in
     hash.cc)

   Nearly all prototypes container classes support container traversal
via `Pix' pseudo indices, as described elsewhere.

   All object containers must perform either a `X::X(X&)' (or `X::X()'
followed by `X::operator =(X&)') to copy objects into containers.  (The
latter form is used for containers built from C++ arrays, like
`VHSets'). When containers are destroyed, they invoke `X::~X()'.  Any
objects used in containers must have well behaved constructors and
destructors. If you want to create containers that merely reference
(point to) objects that reside elsewhere, and are not copied or
destroyed inside the container, you must use containers of pointers,
not containers of objects.

   All prototypes are designed to generate *HOMOGENOUS* container
classes.  There is no universally applicable method in C++ to support
heterogenous object collections with elements of various subclasses of
some specified base class. The only way to get heterogenous structures
is to use collections of pointers-to-objects, not collections of objects
(which also requires you to take responsibility for managing storage for
the objects pointed to yourself).

   For example, the following usage illustrates a commonly encountered
danger in trying to use container classes for heterogenous structures:

     class Base { int x; ...}
     class Derived : public Base { int y; ... }
     
     BaseVHSet s; // class BaseVHSet generated via something like
                  // `genclass Base ref VHSet'
     
     void f()
     {
       Base b;
       s.add(b); // OK
     
       Derived d;
       s.add(d);  // (CHOP!)
     }

   At the line flagged with `(CHOP!)', a `Base::Base(Base&)' is called
inside `Set::add(Base&)'--*not* `Derived::Derived(Derived&)'.
Actually, in `VHSet', a `Base::operator =(Base&)', is used instead to
place the element in an array slot, but with the same effect.  So only
the Base part is copied as a `VHSet' element (a so-called
chopped-copy). In this case, it has an `x' part, but no `y' part; and a
Base, not Derived, vtable. Objects formed via chopped copies are rarely
sensible.

   To avoid this, you must resort to pointers:

     typedef Base* BasePtr;
     
     BasePtrVHSet s; // class BaseVHSet generated via something like
                     // `genclass BasePtr val VHSet'
     
     void f()
     {
       Base* bp = new Base;
       s.add(b);
     
       Base* dp = new Derived;
       s.add(d);  // works fine.
     
       // Don't forget to delete bp and dp sometime.
       // The VHSet won't do this for you.
     }

Example
=======

   The prototypes can be difficult to use on first attempt. Here is an
example that may be helpful. The utilities in the `proto-kit' simplify
much of the actions described, but are not used here.

   Suppose you create a class `Person', and want to make an Map that
links the social security numbers associated with each person. You start
off with a file `Person.h'


     #include <String.h>
     
     class Person
     {
       String nm;
       String addr;
       //...
     public:
       const String& name() { return nm; }
       const String& address() { return addr; }
       void          print() { ... }
       //...
     }

   And in file `SSN.h',

     typedef unsigned int SSN;

   Your first decision is what storage/usage strategy to use. There are
several reasonable alternatives here: You might create an "object
collection" of Persons, a "pointer collection" of pointers-to-Persons,
or even a simple String map, housing either copies of pointers to the
names of Persons, since other fields are unused for purposes of the
Map. In an object collection, instances of class Person "live" inside
the Map, while in a pointer collection, the instances live elsewhere.
Also, as above, if instances of subclasses of Person are to be used
inside the Map, you must use pointers. In a String Map, the same
difference holds, but now only for the name fields. Any of these
choices might make sense in particular applications.

   The second choice is the Map implementation strategy. Either a tree
or a hash table might make sense. Suppose you want an AVL tree Map.
There are two things to now check. First, as an object collection, the
AVLMap requires that the elsement class contain an `X(X&)' constructor.
In C++, if you don't specify such a constructor, one is constructed for
you, but it is a very good idea to always do this yourself, to avoid
surprises. In this example, you'd use something like
     class Person
     { ...;
         Person(const Person& p) :nm(p.nm), addr(p.addr) {}
     };

   Also, an AVLMap requires a comparison function for elements in order
to maintain order. Rather than requiring you to write a particular
comparison function, a `defs' file is consulted to determine how to
compare items. You must create and edit such a file.

   Before creating `Person.defs.h', you must first make one additional
decision. Should the Map member functions like `m.contains(p)' take
arguments (`p') by reference (i.e., typed as `int Map::contains(const
Person& p)' or by value (i.e., typed as `int Map::contains(const Person
p)'. Generally, for user-defined classes, you want to pass by
reference, and for builtins and pointers, to pass by value. SO you
should pick by-reference.

   You can now create `Person.defs.h' via `genclass Person ref defs'.
This creates a simple skeleton that you must edit. First, add `#include
"Person.h"' to the top. Second, edit the `<T>CMP(a,b)' macro to compare
on name, via

     #define <T>CMP(a, b) ( compare(a.name(), b.name()) )

which invokes the `int compare(const String&, const String&)' function
from `String.h'. Of course, you could define this in any other way as
well. In fact, the default versions in the skeleton turn out to be OK
(albeit inefficient) in this particular example.

   You may also want to create file `SSN.defs.h'. Here, choosing
call-by-value makes sense, and since no other capabilities (like
comparison functions) of the SSNs are used (and the defaults are OK
anyway), you'd type

     genclass SSN val defs

and then edit to place `#include "SSN.h"' at the top.

   Finally, you can generate the classes. First, generate the base
class for Maps via

     genclass -2 Person ref SSN val Map

This generates only the abstract class, not the implementation, in file
`Person.SSN.Map.h' and `Person.SSN.Map.cc'.  To create the AVL
implementation, type

     genclass -2 Person ref SSN val AVLMap

This creates the class `PersonSSNAVLMap', in `Person.SSN.AVLMap.h' and
`Person.SSN.AVLMap.cc'.

   To use the AVL implementation, compile the two generated `.cc'
files, and specify `#include "Person.SSN.AVLMap.h"' in the application
program.  All other files are included in the right ways automatically.

   One last consideration, peculiar to Maps, is to pick a reasonable
default contents when declaring an AVLMap. Zero might be appropriate
here, so you might declare a Map,

     PersonSSNAVLMap m((SSN)0);

   Suppose you wanted a `VHMap' instead of an `AVLMap' Besides
generating different implementations, there are two differences in how
you should prepare the `defs' file. First, because a VHMap uses a C++
array internally, and because C++ array slots are initialized
differently than single elements, you must ensure that class Person
contains (1) a no-argument constructor, and (2) an assignment operator.
You could arrange this via

     class Person
     { ...;
         Person() {}
       void operator = (const Person& p) { nm = p.nm; addr = p.addr; }
     };

   (The lack of action in the constructor is OK here because `Strings'
possess usable no-argument constructors.)

   You also need to edit `Person.defs.h' to indicate a usable hash
function and default capacity, via something like

     #include <builtin.h>
     #define <T>HASH(x)  (hashpjw(x.name().chars()))
     #define DEFAULT_INITIAL_CAPACITY 1000

   Since the `hashpjw' function from `builtin.h' is appropriate here.
Changing the default capacity to a value expected to exceed the actual
capacity helps to avoid "hidden" inefficiencies when a new VHMap is
created without overriding the default, which is all too easy to do.

   Otherwise, everything is the same as above, substituting `VHMap' for
`AVLMap'.