riedl@cs.purdue.EDU (John T Riedl) (09/28/89)
In article <8909281301.AA20359@g.oswego.edu> dl@G.OSWEGO.EDU (Doug Lea) writes: > We've been unhappy with the classes generated by genclass because each > type needs to be separately generated, including the entire > ... First, please use bug-lib-g++ for libg++-related questions. (There is no info-lib-g++, just use the bug list.) Possibly the best solution in your case would be to 1) have all your classes be derived from a common base, that includes a virtual int compare(Base* b); 2) Have all your containers be of Base*'s (suitably typedef'ed) 3) Edit the CMP(a, b) macro to call a->compare. And/Or similarly for the EQ macros, etc. This gets you heterogenous containers. If you want homogenous containers, then you probably want to live with multiple implementations. The main disadvantage of the current container library is that you can't readily set things up so that you can have subclasses of Set, each of which shares the basic Set code but operates on pointers of an *unrelated* different type. I don't think that full C++ support for generics will happen in the near future. -Doug This is an interesting suggestion, but as you point out only works for related types. We implemented an alternative approach based on storing pointers in the Set object to the compare and hash functions for the contained class. The constructor for the Set subclass requires pointers to the two functions, and stores them in the Set superclass. Our basic set type is void*, so Sets act as containers for arbitrary objects. In effect, we have an implementation of generics in which the type is determined by the compare and hash functions supplied to the constructor. We tested our idea for the OSLSet and CHSet subclasses, and it does exactly what we want. (Well, I'd prefer a true generic, but ...) The changes are simple, so I've appended them to this message. I'd like to suggest that generic sets implemented in this way be supplied with libg++. It seems to me that when a programmer first starts using libg++ she wants to have usable versions of the important classes available immediately. Our implementation provides a generic version of each class, with the user only supplying a compare and hash function. A library of container classes set up in this way could be used from any program, without even recompiling the container class. The programmer can figure out how to use genclass later to get homogenous containers for performance and type checking benefits. Thanks, John Riedl (Srinivasan Jagannathan deserves equal credit for the implemenation, but don't blame him for this message.) ---------------- This is a list of the changes needed to change a Set class to the generic style. In generic-style, each Set consists of void * elements. The comparison and hash operators are passed to the constructor during initialization (by the user) and saved in instance variables of the Set supertype. These functions can then be used by the data structure manipulation and lookup routines. Thus, such a set can be used to store pointers to arbitrary types, with the compare and hash functions for the type written by the user. John Riedl riedl@cs.purdue.edu Srinivasan Jagannathan sja@cs.purdue.edu * generate a Set class, including all member classes and the superclass Set. For instance, for the class OSLSet: genclass ent val OSLSet # ordered set class genclass ent val SLList # ... based on singly linked lists genclass ent val Set # ... using Set superclass genclass ent val defs # #define's for new class * modify the defs file for the new class (ent.defs.h). Ent must be typedef'd to a void *, typedef's for the pointers to the compare and hash functions and the #define'd hash and compare functions must be modified to use the new class members: typedef void *ent; typedef void *(*compareFunc)(void *, void *); typedef int *(*hashFunc)(void *); // comparison operator #ifndef entCMP #define entCMP(a, b) ((*compare)(a, b)) #endif // equality operator #ifndef entEQ #define entEQ(a, b) (entCMP(a, b) == 0) #endif // less-than-or-equal #ifndef entLE #define entLE(a, b) (entCMP(a, b) <= 0) #endif // hash function #ifndef entHASH #define entHASH(x) (*hash)(x) #endif Note that the order of the comparisons is changed so that entCMP is defined first so it can be used in endEQ and entLE. If performance is important the implementation can be changed to pass entEQ and entLE funtions, and entCMP can be derived. Our implementation doubles the cost of entEQ and entLE, but only has to store one comparison function. entHash only needs to be modified for Set types that use member types that use hashing (e.g., CHSet). * The Set superclass needs new members to contain the hash and compare functions. Change the list of protected variables in ent.Set.h to look like (count was already there): protected: int count; hashFunc hash; compareFunc compare; * The constructor for the new set subclass (e.g., OSLSet) needs to have the hash and compare functions as arguments. Note that if the particular Set type does not need a hash function an additional constructor can be supported that only requires a compare function. For compatibility it is useful for the set constructor to accept a hash function even if it doesn't use it: inline entOSLSet::entOSLSet(compareFunc cF, hashFunc hF) : p() { count = 0; compare = cF; hash = hF; } inline entOSLSet::entOSLSet(compareFunc cF) : p() { count = 0; compare = cF} inline entOSLSet::entOSLSet(const entOSLSet& s) : p(s.p) { count = s.count; compare = s.compare; hash = s.hash; } Of course the declaration of the constructors has to be changed correspondingly. * we had to add an #include for ent.defs.h to ent.SLList.h. Why wasn't this generated automatically?
T.Day@ucl-cs.UUCP (10/04/89)
From: Tim Day <T.Day@uk.ac.ucl.cs>
You can take a lot of the pain out of genclass with makefile rules
e.g from my own setup for bags: (works OK on Gnu make 3.54)
Note that
$(GDEP) is the name of a file which can be touched to cause all genclassed
code to be rebuilt.
$(Gcomp) is the g++ compile macro (= $(C++) $(C++FLAGS) etc)
Bags/Lists of Ptrs are pass by value (created by $(genclassV)).
Anything else is pass by reference (created by $(genclassR)).
useful.h is included everywhere
The $(genclass ) macros...
genclass the required class
Insert a #include for the name of the ``contained'' class
Insert a #include "useful.h"
Touch a .cc file in case genclass didn't produce one
The result is that you can get all the .SLList, .Bag and .SLBag files generated
just by mentioning a .SLBag.h dependency. (Of course you still have to
remember to archive or link all three .o files)
define genclassR
genclass $(basename $(basename $(notdir $@))) ref $(suffix $(basename $(notdir $@)))
prepend '#include "$(basename $(basename $(notdir $@))).h"' $(basename $(notdir $@)).h
prepend '#include "useful.h"' $(basename $(notdir $@)).h
touch $(basename $(notdir $@)).cc
endef
define genclassV
genclass $(basename $(basename $(notdir $@))) val $(suffix $(basename $(notdir $@)))
prepend '#include "$(basename $(basename $(notdir $@))).h"' $(basename $(notdir $@)).h
prepend '#include "useful.h"' $(basename $(notdir $@)).h
touch $(basename $(notdir $@)).cc
endef
%Ptr.SLList.h %Ptr.SLList.cc: $(GDEP)
$(genclassV)
%Ptr.SLList.o: useful.h %Ptr.h %Ptr.defs.h %Ptr.SLList.h %Ptr.SLList.cc
$(Gcomp)
%Ptr.Bag.h %Ptr.Bag.cc: $(GDEP)
$(genclassV)
%Ptr.Bag.o: useful.h %Ptr.h %Ptr.defs.h %Ptr.Bag.h %Ptr.Bag.cc
$(Gcomp)
%Ptr.SLBag.h %Ptr.SLBag.cc: $(GDEP) %Ptr.SLList.h %Ptr.Bag.h
$(genclassV)
%Ptr.SLBag.o: $(GDEP) useful.h %Ptr.h %Ptr.defs.h %Ptr.SLList.h %Ptr.Bag.h %Ptr.SLBag.h %Ptr.SLBag.cc
$(Gcomp)
%.SLList.h %.SLList.cc: $(GDEP)
$(genclassR)
%.SLList.o: useful.h %.h %.defs.h %.SLList.h %.SLList.cc
$(Gcomp)
%.Bag.h %.Bag.cc: $(GDEP)
$(genclassR)
%.Bag.o: useful.h %.h %.defs.h %.Bag.h %.Bag.cc
$(Gcomp)
%.SLBag.h %.SLBag.cc: $(GDEP) %.SLList.h %.Bag.h
$(genclassR)
%.SLBag.o: $(GDEP) useful.h %.h %.defs.h %.SLList.h %.Bag.h %.SLBag.h %.SLBag.cc
$(Gcomp)
You'll probably have to declare all the .h files you create as precious,
otherwise make regards them as intermediate and deletes them after its built
the .o... not much use for libraries. I think make can also get a little
confused by genclass creating two files at once. You need slightly
different versions of the genclass macros for bags of builtins (e.g int) or
supplied classes (e.g String).
My favourite class ? String.%Ptr.SplayMap, v. useful for writing parser type
things
+-----------------------------------------------------------------------------+
Tim Day | Meet every second in life as challenge;
Department of Photogrammetry | Respond fully to whatever happens
UCL, Gower St., London WC1E 6BT | without anxiety, or complaint, or clinging
+-----------------------------------------------------------------------------+