15.9.1. An Object-Oriented Solution

We might think that we should use the TextQuery class from §12.3.2 (p. 487) to represent our word query and derive our other queries from that class.

However, this design would be flawed. To see why, consider a Not query. A Word query looks for a particular word. In order for a Not query to be a kind of Word query, we would have to be able to identify the word for which the Not query was searching. In general, there is no such word. Instead, a Not query has a query (a Word query or any other kind of query) whose value it negates. Similarly, an And query and an Or query have two queries whose results it combines.

This observation suggests that we model our different kinds of queries as independent classes that share a common base class:

WordQuery // Daddy
NotQuery  // ~Alice
OrQuery   // hair | Alice
AndQuery  // hair & Alice

These classes will have only two operations:

• eval, which takes a TextQuery object and returns a QueryResult. The eval function will use the given TextQuery object to find the query’s the matching lines.

• rep, which returns the string representation of the underlying query. This function will be used by eval to create a QueryResult representing the match and by the output operator to print the query expressions.

Abstract Base Class

As we’ve seen, our four query types are not related to one another by inheritance; they are conceptually siblings. Each class shares the same interface, which suggests that we’ll need to define an abstract base class (§15.4, p. 610) to represent that interface. We’ll name our abstract base class Query_base, indicating that its role is to serve as the root of our query hierarchy.

Our Query_base class will define eval and rep as pure virtual functions (§15.4, p. 610). Each of our classes that represents a particular kind of query must override these functions. We’ll derive WordQuery and NotQuery directly from Query_base. The AndQuery and OrQuery classes share one property that the other classes in our system do not: Each has two operands. To model this property, we’ll define another abstract base class, named BinaryQuery, to represent queries with two operands. The AndQuery and OrQuery classes will inherit from BinaryQuery, which in turn will inherit from Query_base. These decisions give us the class design represented in Figure 15.2.

Figure 15.2. Query_base Inheritance Hierarchy

Hiding a Hierarchy in an Interface Class

Our program will deal with evaluating queries, not with building them. However, we need to be able to create queries in order to run our program. The simplest way to do so is to write C++ expressions to create the queries. For example, we’d like to generate the compound query previously described by writing code such as

Query q = Query("fiery") & Query("bird") | Query("wind");

This problem description implicitly suggests that user-level code won’t use the inherited classes directly. Instead, we’ll define an interface class named Query, which will hide the hierarchy. The Query class will store a pointer to Query_base. That pointer will be bound to an object of a type derived from Query_base. The Query class will provide the same operations as the Query_base classes: eval to evaluate the associated query, and rep to generate a string version of the query. It will also define an overloaded output operator to display the associated query.

Users will create and manipulate Query_base objects only indirectly through operations on Query objects. We’ll define three overloaded operators on Query objects, along with a Query constructor that takes a string. Each of these functions will dynamically allocate a new object of a type derived from Query_base:

• The & operator will generate a Query bound to a new AndQuery.

• The | operator will generate a Query bound to a new OrQuery.

• The ~ operator will generate a Query bound to a new NotQuery.

• The Query constructor that takes a string will generate a new WordQuery.

Understanding How These Classes Work

It is important to realize that much of the work in this application consists of building objects to represent the user’s query. For example, an expression such as the one above generates the collection of interrelated objects illustrated in Figure 15.3.

Figure 15.3. Objects Created by Query Expressions

Once the tree of objects is built up, evaluating (or generating the representation of) a query is basically a process (managed for us by the compiler) of following these links, asking each object to evaluate (or display) itself. For example, if we call eval on q (i.e., on the root of the tree), that call asks the OrQuery to which q points to eval itself. Evaluating this OrQuery calls eval on its two operands—on the AndQuery and the WordQuery that looks for the word wind. Evaluating the AndQuery evaluates its two WordQuerys, generating the results for the words fiery and bird, respectively.

When new to object-oriented programming, it is often the case that the hardest part in understanding a program is understanding the design. Once you are thoroughly comfortable with the design, the implementation flows naturally. As an aid to understanding this design, we’ve summarized the classes used in this example in Table 15.1 (overleaf).

Table 15.1. Recap: Query Program Design