From: rmartin@thor.Rational.COM (Bob Martin)
Newsgroups: comp.lang.c++
Subject: Re: HELP NEEDED - INHERITING A LIST AND SORTING IT - C++
Date: 27 Aug 92 15:07:55 GMT


These are traditional problems with C++'s contravariant virtual functions.
I have embedded a few suggestions below.

int376f@aurora.cc.monash.edu.au (Jamie Scuglia) writes:


|Hi!  I have a small problem with some C++ code I am writing, to handle
|a football tipping competion.  I have a ladder structure, which is to
|hold ladders (positions) of participants in the tipping competition, as well
|as a ladder of the football teams.  My basic class structure consists
|of 3 classes for the ladder system.  

|- A base class, called LADDER, which defines the basic attributes
|  of a ladder, including a definition for a simple linked list, and
|  it also has a member function to sort the ladder.

|- A derived class called TEAM_LADDER which includes some more attributes
|  related to football team statistics that a ladder holds.

|- A second derived class (from LADDER), called PLAYER_LADDER, which
|  has a more specilized attributes relating to player performance in
|  the tipping competition.

|The set-up of these classes looks like this: (with '....' = other stuff)

Note the changes that I have made to this code.  Specifically the
inclusion of a pure virtual Compare function in LADDER, and the
corresponding changes in the derived classes.


|------------------------------------------------------------------------
|class LADDER
|{
|   protected:
|	char name[60];
|	int points;
|	float percentage;
|	LADDER *next_entry;
|	LADDER *last_entry; 

|   public:
|	LADDER(char n[], int pts, float p, LADDER *next, LADDER* last);
        virtual int Compare(const LADDER&) const = 0;
|	virtual LADDER *Sort_ladder(LADDER *ladder);
|};

|class PLAYER_LADDER : public LADDER
|{	
|   private:
|	char login_name[12]; 

|   public:
|	........
|	void Save_ladder(PLAYER_LADDER *ladder);
|	int Compare(const LADDER&) const;
|	.........
|};

|class TEAM_LADDER : public LADDER
|{
|   private:
|      float match_ratio;
|      int games_played;
|      ......

|   public:
|      ......
|      void Save_ladder(TEAM_LADDER *ladder);
|      int Compare(const LADDER&) const;
|      ......
|};
|------------------------------------------------------------------------

|Now, the problem occurs in the function PLAYER_LADDER:Save_ladder,
|(and TEAM_LADDER::Save_ladder).
|To save the ladder, I need to traverse the list I inherited from
|the base class LADDER.  *BUT*, I can't do that (the compiler complains)
|because in Save_ladder there is this code:

|        PLAYER_LADDER *player_ladder;
|        ......
|        player_ladder = player_ladder->next;  /* next ladder entry */

|which is no good, because the "next" pointer in PLAYER_LADDER actually
|points to the base class LADDER, not PLAYER_LADDER as I wanted it to, 
|even though I inherited the basic list structure from the class LADDER.
|So, the compiler tells me it can't assign a type PLAYER_LADDER to LADDER
|when I try to traverse the list that I inherited.  And I can't change the
|"player_ladder" pointer to type LADDER (base-class) because then I would
|lose the "login_name" field I added to PLAYER_LADDER.

Right.  This is contravariance, the types of virtual functions do not
vary with the type of the class that contains them.  There are several
ways around this, the simplest and most dangerous being to downcast:

	PLAYER_LADDER* pl;
        ...
        pl = (PLAYER_LADDER*)(pl->next);

This is dangerous because you are losing a little type safety.  You
must make the assumption that the 'next' element will always really
point to a PLAYER_LADDER...

There are better ways to address this problem.  Templates being one of
them.  Templates do not suffer so much from contravariance, their
arguments are covariant.  In an industrial environment I would opt for
a template solution, or some other solution that preserved type
safety.  But if your application is informal, then downcasting is
probably sufficient...  


|You also might notice that I have a "Compare" function in
|PLAYER_LADDER and TEAM_LADDER classes to compare two ladder entries
|to see if they are in the correct order.  Since a TEAM_LADDER and
|a PLAYER_LADDER are sorted according to different criteria, I wrote
|a version for each of these 2 classes.  Now, the function Sort_ladder
|in the base class has an awful lot of trouble finding the correct Compare
|function. 

Right.  Contravariance again. This is why I put the pure virtual
Compare function into LADDER.  By sacrificing a little type safety you
can write your Sort function so that it upcasts the PLAYER_LADDER or
TEAM_LADDER pointers to LADDER poitners.  Then in each of the derived
Compare function, you can downcast them again.  In this manner you can
get a single Sort method in LADDER to do the sorting in both derived
lists.

Again, there are better ways, and again using templates is one of
them.

------------------

Now let me digress just a bit.  The structure you have built is very
common, and it possesses a common flaw.  You are mixing two
abstractions into a single class.  The first abstraction is that of an
element of a ladder.  The second abstraction is that of the ladder
itself, i.e. the list of ladder elements preserved in some order.

I recommend, as a learning excersize, that you try to design this
application using the two concepts rather than mixing them into a
single class.  Create LADDER_ENTRY as an abstract base, and then
derive PLAYER_LADDER_ENDTRY and TEAM_LADDER_ENTRY from it.  Also
create a LADDER class to represent the ordered list.  You might need
to derive PLAYER_LADDER and TEAM_LADDER from it, and you might not...
Also, you might want to come up with a LADDER_ENTRY_LIST class which
supports the ordered nature of LADDER_ENTRY objects, but does not
encapsulate any of the other attributes of a LADDER.  The LADDER class
would then contain at least one instance of such a list...


Just some ideas....


--
Robert Martin                        Training courses offered in:
R. C. M. Consulting                       Object Oriented Analysis
2080 Cranbrook Rd.                        Object Oriented Design
Green Oaks, Il 60048 (708) 918-1004       C++
Newsgroups: comp.lang.c++