Alice Emma has long flowing red hair.
Her Daddy says when the wind blows
through her hair, it looks almost alive,
like a fiery bird in flight.
A beautiful fiery bird, he tells her,
magical but untamed.
"Daddy, shush, there is no such thing,"
she tells him, at the same time wanting
him to tell her more.
Shyly, she asks, "I mean, Daddy, is there?"

Our system should support the following queries:

• Word queries find all the lines that match a given string:

Executing Query for:
Daddy Daddy occurs 3 times
(line 2) Her Daddy says when the wind blows
(line 7) "Daddy, shush, there is no such thing,"
(line 10) Shyly, she asks, "I mean, Daddy, is there?"

• Not queries, using the ~ operator, yield lines that don’t match the query:

Executing Query for: ~(Alice)
~(Alice) occurs 9 times
(line 2) Her Daddy says when the wind blows
(line 3) through her hair, it looks almost alive,
(line 4) like a fiery bird in flight.
...

• Or queries, using the | operator, return lines matching either of two queries:

Executing Query for: (hair | Alice)
(hair | Alice) occurs 2 times
(line 1) Alice Emma has long flowing red hair.
(line 3) through her hair, it looks almost alive,

• And queries, using the & operator, return lines matching both queries:

Executing query for: (hair & Alice)
(hair & Alice) occurs 1 time
(line 1) Alice Emma has long flowing red hair.

Moreover, we want to be able to combine these operations, as in

fiery & bird | wind

Our output will print the query, using parentheses to indicate the way in which the query was interpreted. As with our original implementation, our system will display lines in ascending order and will not display the same line more than once.

15.9.1. An Object-Oriented Solution

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");

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

Figure 15.3. Objects Created by Query Expressions

15.9.2. The Query_base and Query Classes

We’ll start our implementation by defining the Query_base class:

// abstract class acts as a base class for concrete query types; all members are private
class Query_base {
    friend class Query;
protected:
    using line_no = TextQuery::line_no; // used in the eval functions
    virtual ~Query_base() = default;
private:
    // eval returns the QueryResult that matches this Query
    virtual QueryResult eval(const TextQuery&) const = 0;
    // rep is a string representation of the query
    virtual std::string rep() const = 0;
};

The Query class provides the interface to (and hides) the Query_base inheritance hierarchy. Each Query object will hold a shared_ptr to a corresponding Query_base object. Because Query is the only interface to the Query_base classes, Query must define its own versions of eval and rep.

The Query constructor that takes a string will create a new WordQuery and bind its shared_ptr member to that newly created object. The &, |, and ~ operators will create AndQuery, OrQuery, and NotQuery objects, respectively. These operators will return a Query object bound to its newly generated object. To support these operators, Query needs a constructor that takes a shared_ptr to a Query_base and stores its given pointer. We’ll make this constructor private because we don’t intend general user code to define Query_base objects. Because this constructor is private, we’ll need to make the operators friends.

Given the preceding design, the Query class itself is simple:

// interface class to manage the Query_base inheritance hierarchy
class Query {
    // these operators need access to the shared_ptr constructor
    friend Query operator~(const Query &);
    friend Query operator|(const Query&, const Query&);
    friend Query operator&(const Query&, const Query&);
public:
    Query(const std::string&);  // builds a new WordQuery
    // interface functions: call the corresponding Query_base operations
    QueryResult eval(const TextQuery &t) const
                            { return q->eval(t); }
    std::string rep() const { return q->rep(); }
private:
    Query(std::shared_ptr<Query_base> query): q(query) { }
    std::shared_ptr<Query_base> q;
};

In the public interface for Query, we declare, but cannot yet define, the constructor that takes a string. That constructor creates a WordQuery object, so we cannot define this constructor until we have defined the WordQuery class.

The other two public members represent the interface for Query_base. In each case, the Query operation uses its Query_base pointer to call the respective (virtual) Query_base operation. The actual version that is called is determined at run time and will depend on the type of the object to which q points.

The Query Output Operator

The output operator is a good example of how our overall query system works:

std::ostream &
operator<<(std::ostream &os, const Query &query)
{
    // Query::rep makes a virtual call through its Query_base pointer to rep()
    return os << query.rep();
}

When we print a Query, the output operator calls the (public) rep member of class Query. That function makes a virtual call through its pointer member to the rep member of the object to which this Query points. That is, when we write

Query andq = Query(sought1) & Query(sought2);
cout << andq << endl;

the output operator calls Query::rep on andq. Query::rep in turn makes a virtual call through its Query_base pointer to the Query_base version of rep. Because andq points to an AndQuery object, that call will run AndQuery::rep.

The most interesting part of the classes derived from Query_base is how they are represented. The WordQuery class is most straightforward. Its job is to hold the search word.

The other classes operate on one or two operands. A NotQuery has a single operand, and AndQuery and OrQuery have two operands. In each of these classes, the operand(s) can be an object of any of the concrete classes derived from Query_base: A NotQuery can be applied to a WordQuery, an AndQuery, an OrQuery, or another NotQuery. To allow this flexibility, the operands must be stored as pointers to Query_base. That way we can bind the pointer to whichever concrete class we need.

However, rather than storing a Query_base pointer, our classes will themselves use a Query object. Just as user code is simplified by using the interface class, we can simplify our own class code by using the same class.

Now that we know the design for these classes, we can implement them.

The WordQuery Class

A WordQuery looks for a given string. It is the only operation that actually performs a query on the given TextQuery object:

class WordQuery: public Query_base {
    friend class Query; // Query uses the WordQuery constructor
    WordQuery(const std::string &s): query_word(s) { }
    // concrete class: WordQuery defines all inherited pure virtual functions
    QueryResult eval(const TextQuery &t) const
                     { return t.query(query_word); }
    std::string rep() const { return query_word; }
    std::string query_word;    // word for which to search
};

Like Query_base, WordQuery has no public members; WordQuery must make Query a friend in order to allow Query to access the WordQuery constructor.

Each of the concrete query classes must define the inherited pure virtual functions, eval and rep. We defined both operations inside the WordQuery class body: eval calls the query member of its given TextQuery parameter, which does the actual search in the file; rep returns the string that this WordQuery represents (i.e., query_word).

Having defined the WordQuery class, we can now define the Query constructor that takes a string:

inline
Query::Query(const std::string &s): q(new WordQuery(s)) { }

This constructor allocates a WordQuery and initializes its pointer member to point to that newly allocated object.

The NotQuery Class and the ~ Operator

The ~ operator generates a NotQuery, which holds a Query, which it negates:

class NotQuery: public Query_base {
    friend Query operator~(const Query &);
    NotQuery(const Query &q): query(q) { }
    // concrete class: NotQuery defines all inherited pure virtual functions
    std::string rep() const {return "~(" + query.rep() + ")";}
    QueryResult eval(const TextQuery&) const;
    Query query;
};
inline Query operator~(const Query &operand)
{
    return std::shared_ptr<Query_base>(new NotQuery(operand));
}

Because the members of NotQuery are all private, we start by making the ~ operator a friend. To rep a NotQuery, we concatenate the ~ symbol to the representation of the underlying Query. We parenthesize the output to ensure that precedence is clear to the reader.

It is worth noting that the call to rep in NotQuery’s own rep member ultimately makes a virtual call to rep: query.rep() is a nonvirtual call to the rep member of the Query class. Query::rep in turn calls q->rep(), which is a virtual call through its Query_base pointer.

The ~ operator dynamically allocates a new NotQuery object. The return (implicitly) uses the Query constructor that takes a shared_ptr<Query_base>. That is, the return statement is equivalent to

// allocate a new NotQuery object
// bind the resulting NotQuery pointer to a shared_ptr<Query_base
shared_ptr<Query_base> tmp(new NotQuery(expr));
return Query(tmp); // use the Query constructor that takes a shared_ptr

To rep a BinaryOperator, we generate the parenthesized expression consisting of the representation of the left-hand operand, followed by the operator, followed by the representation of the right-hand operand. As when we displayed a NotQuery, the calls to rep ultimately make virtual calls to the rep function of the Query_base objects to which lhs and rhs point.

The AndQuery and OrQuery Classes and Associated Operators

The AndQuery and OrQuery classes, and their corresponding operators, are quite similar to one another:

class AndQuery: public BinaryQuery {
    friend Query operator& (const Query&, const Query&);
    AndQuery(const Query &left, const Query &right):
                        BinaryQuery(left, right, "&") { }
    // concrete class: AndQuery inherits rep and defines the remaining pure virtual
    QueryResult eval(const TextQuery&) const;
};
inline Query operator&(const Query &lhs, const Query &rhs)
{
    return std::shared_ptr<Query_base>(new AndQuery(lhs, rhs));
}

class OrQuery: public BinaryQuery {
    friend Query operator|(const Query&, const Query&);
    OrQuery(const Query &left, const Query &right):
                BinaryQuery(left, right, "|") { }
    QueryResult eval(const TextQuery&) const;
};
inline Query operator|(const Query &lhs, const Query &rhs)
{
    return std::shared_ptr<Query_base>(new OrQuery(lhs, rhs));
}

These classes make the respective operator a friend and define a constructor to create their BinaryQuery base part with the appropriate operator. They inherit the BinaryQuery definition of rep, but each overrides the eval function.

Like the ~ operator, the & and | operators return a shared_ptr bound to a newly allocated object of the corresponding type. That shared_ptr gets converted to Query as part of the return statement in each of these operators.

15.9.4. The eval Functions

The eval functions are the heart of our query system. Each of these functions calls eval on its operand(s) and then applies its own logic: The OrQuery eval operation returns the union of the results of its two operands; AndQuery returns the intersection. The NotQuery is more complicated: It must return the line numbers that are not in its operand’s set.

// returns the union of its operands' result sets
QueryResult
OrQuery::eval(const TextQuery& text) const
{
    // virtual calls through the Query members, lhs and rhs
    // the calls to eval return the QueryResult for each operand
    auto right = rhs.eval(text), left = lhs.eval(text);
    // copy the line numbers from the left-hand operand into the result set
    auto ret_lines =
         make_shared<set<line_no>>(left.begin(), left.end());
    // insert lines from the right-hand operand
    ret_lines->insert(right.begin(), right.end());
    // return the new QueryResult representing the union of lhs and rhs
    return QueryResult(rep(), ret_lines, left.get_file());
}

We initialize ret_lines using the set constructor that takes a pair of iterators. The begin and end members of a QueryResult return iterators into that object’s set of line numbers. So, ret_lines is created by copying the elements from left’s set. We next call insert on ret_lines to insert the elements from right. After this call, ret_lines contains the line numbers that appear in either left or right.

Once we’ve processed all the line numbers, we return a QueryResult containing ret_lines, along with the results of running rep and get_file as in the previous eval functions.