Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!rutgers!mit-eddie!uw-beaver!milton!ns.uoregon.edu!cs.uoregon.edu!mips!sgi!shinobu!odin!sgihub!dragon!xanadu.wpd.sgi.com!pal
From: pal@xanadu.wpd.sgi.com (Anil Pal)
Newsgroups: comp.lang.c++
Subject: Re: Lacking parameterized types and multi-methods....
Message-ID: <1991Mar5.215208.21511@dragon.wpd.sgi.com>
Date: 5 Mar 91 21:52:08 GMT
References: <11687@pasteur.Berkeley.EDU>
Sender: news@dragon.wpd.sgi.com (CNews Account)
Reply-To: pal@sgi.com
Organization: Silicon Graphics, Inc.
Lines: 82

In article <11687@pasteur.Berkeley.EDU>, maverick@fir.Berkeley.EDU (Vance Maverick) writes:
|> 
|> I have a problem for which I have not yet found a clean solution in C++.
|>  In my application, there are various classes of which I wish to keep
|> lists.  So I define a single class List, which handles objects of class
|> Listable, and I make all the things I want lists of (musical notes,
|> names, and other incompatible types) subclasses of Listable.
|> 
|> So far so good; but I want the List code to be able to compare two
|> objects [...].
|> 
|> Does anybody have a suggestion for how to do this "correctly", lacking
|> parameterized types and runtime method selection on multiple arguments? 

Depends on what you mean by "correctly".  I see two cases here, and will
describe the "correct" solution (or my interpretation thereof) for each of
them.

Case 1: Homogeneous lists
    This one is easy.  Use parameterized types (templates, generics).  Yes, I
    know C++ doesn't have them yet, but it will soon (in the standard).  And in
    the meantime, you can fake it with the pre-processor.

Case 2: Heterogeneous lists
    I am assuming here that you want a sorted heterogeneous list, which implies
    that you have some well-defined ordering function that *can* meaningfully
    compare a Name to a Note (to use your example).

    This is not easy to do, but then the requirements aren't trivial.  You
    will, in general, need n-squared comparison functions (where n is the
    number of Listable classes).  And you have to do some manual
    double-dispatching.

    For the sake of an example, let me assume just two classes, Name and Note.
    I also use Comparable instead of Listable as the base class.

    class Comparable {
    public:
	virtual int operator<(Comparable&) = 0;
	virtual int operator<(Name&) = 0;
	virtual int operator<(Note&) = 0;
	// Note - you need to add one more virtual operator
	// for each class derived from Comparable
    };

    class Note : public Comparable {
    public:
	virtual int operator<(Comparable& other);
	virtual int operator<(Name& other);
	virtual int operator<(Note& other);
    };

    int Note::operator<(Comparable& other)
    {
	return ! (other.operator<(*this));
	// Invokes other.operator<(Note&)
    }

    int Note::operator<(Note& other)
    {
	// Actually compare the two Notes, and return appropriate result
    }

    int Note::operator<(Name& other)
    {
	// Now both types are known - Note and Name; do appropriate comparison
    }

    // Similarly for class Name

The key step here is in the Note::operator<(Comparable& other).  At
this point, the type of one operand (the left one) is determined
through the virtual function mechanism.  By reversing the operands at
this point you determine the type of the other operand, also through
the virtual function mechanism.  Once both types are determined, the
two types determine the appropriate one of the n-squared comparison
functions.  This method of dispatching first on one argument type, then
another is referred to as double-dispatching.

-- 
Anil A. Pal,	Silicon Graphics, Inc.
pal@sgi.com	(415)-335-7279