3.3. Designing a Class Hierarchy

Our first thought in terms of a class design is to represent each query operation as an individual class:

NameQuery      // Alice
NotQuery       // ! Alice
OrQuery        // Alice || fiery
AndQuery       // Alice && Daddy

At first blush, this design appears adequate. For example, each class provides an eval() method that solves the query for the operation it represents, and a display_solution() method to display its solution. A solution is represented as a unique collection of line numbers in ascending order.

The eval() method for NameQuery simply returns the numbers of the lines in which the name occurs. The eval() method for OrQuery, on the other hand, must build up a union of the line occurrences of its two operands. The AndQuery and NotQuery classes each must provide a unique implementation of eval() as well.

If the user enters the following query:

untamed || fiery

we create two NameQuery class objects to represent the strings untamed and fiery. We then create an OrQuery class object, passing in these two NameQuery objects as its operands. Next we invoke OrQuery's eval() method to generate a solution. Finally, we call print() to display the solution. In fact, there seems to be no need to introduce object-oriented programming!

This design of four independent classes breaks down when we are handling compound queries such as the following:

Alice || Emma && Weeks

This query consists of two subqueries: an OrQuery object containing two NameQuery operands associated with the strings Alice and Emma, and an AndQuery object. The right-hand operand of the AndQuery object is the NameQuery object associated with the string Weeks. So far, so good: Every operand has been a NameQuery object, and that's easy enough to represent.

The left-hand operand, however, invalidates our simple design:

AndQuery
   // here is the problem!
   OrQuery
      NameQuery ("Alice")
      NameQuery ("Emma")
   NameQuery ("Weeks")

AndQuery's left operand is the OrQuery object. More generally, we realize, the operand of a query object other than NameQuery can be any other query type. How can we internally represent an operand when we don't know what type it needs to be? Or rather, when we know it can be one of several different types? The problem is twofold:

This is where the need for object-oriented programming comes in. Recasting our classes into a query inheritance hierarchy solves both problems.

Through inheritance we define a relationship among the four previously independent query class types. We do this by introducing an abstract Query base class from which the other classes can be derived. Inheritance provides an immediate solution to our first problem: A base-class object can transparently address objects of any of its derived-class types.

Inheritance confers a special type/subtype relationship between a base class and its derived classes. When a base-class object is initialized or assigned with a class derived from it, an implicit conversion is automatically carried out. In our Query class hierarchy, an object of type Query can transparently refer to an OrQuery, AndQuery, NotQuery, or NameQuery object.

To indicate that one class is inheriting from another, we write the following:

class NotQuery : Query

The colon following the NotQuery class name indicates that it is inheriting from the Query class name that follows. NotQuery is the derived class; Query is its immediate base class. The two primary constraints on a base class are

Before we created our Query class hierarchy, the only way to define a function that could accept each of the query class types was to explicitly overload the function to accept each instance:

class testQuery
{

    public static void eval_print( OrQuery q )
      { q.eval(); q.print_solution(); }
      
    public static void eval_print( AndQuery q )
      { q.eval(); q.print_solution(); }

    public static void eval_print( NotQuery q )
      { q.eval(); q.print_solution(); }

    public static void eval_print( NameQuery q )
      { q.eval(); q.print_solution(); }

    // ...
}

Once we introduce our abstract Query base class and derive each of the query types from it, creating an inheritance hierarchy, we can reduce our four functions to a single instance:

class testQuery
{
    public static void eval_print( Query q )
      { q.eval(); q.print_solution(); }

    public static void Main()
    {
      NameQuery nq1 = new NameQuery( "Mason" );
      NameQuery nq2 = new NameQuery( "Dixon" );
      AndQuery  aq  = new AndQuery( nq1, nq2 );
      OrQuery   oq  = new OrQuery( nq1, nq2 );
      NotQuery  nq  = new NotQuery( nq1, nq2 );

      // OK: automatic conversion from a
      //     derived class to its base class

      eval_print( nq1 );   eval_print( aq );
      eval_print( nq );    eval_print( oq );

      // error: string is not derived from Query;
      //        no conversion
      eval_print( "MasonDixon" );
    }
}

A derived class is implicitly converted into an object of its base class when necessary, such as when we invoke eval_print(). However, when we attempt to assign a string object to the Query base-class object, the assignment fails. There is no relationship between the Query and string types.

What would you expect to happen if we assign two derived-class instances of a common base class to one another—for example, an OrQuery object to an object of type AndQuery? Once again, the assignment fails; no special relationship is defined between the derived classes of a common subtype.

Inheritance solves the problem of transparently referring to a family of types. However, it does not solve the problem of transparently programming these types; for this we need dynamic binding. Through dynamic binding, the invocation of eval() through the Query object, q.eval(), invokes the eval() function associated with the actual derived-class object to which q refers rather than the instance associated with the Query class.

By default, a member function is resolved through static binding—that is, at compile time based on the type of object through which the method is invoked. In other words, by default, q.eval() invokes the eval() method of q's class type, which is Query.

To have a member function resolved through dynamic binding—that is, during runtime on the basis of the type of the object referred to—we must explicitly label the member function as virtual. Otherwise it is treated as nonvirtual. One part of object-oriented design under C# is deciding whether a base-class member function should be identified as virtual. (Note that static member functions do not support dynamic binding. The reason is that a static member function is not invoked through a class object.)

The design of an inheritance hierarchy, such as our Query class hierarchy, requires two primary design steps: (1) factoring a set of shared operations into an abstract base-class interface, and (2) deciding which of those methods (perhaps all) require dynamic binding. Before we turn to the design and implementation of that hierarchy, we need to step back a moment and reexamine the C# unified type system.