eval
FunctionsThe 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.
To support the processing in the eval
functions, we need to use the version of QueryResult
that defines the members we added in the exercises to §12.3.2 (p. 490). We’ll assume that QueryResult
has begin
and end
members that will let us iterate through the set
of line numbers that the QueryResult
holds. We’ll also assume that QueryResult
has a member named get_file
that returns a shared_ptr
to the underlying file on which the query was executed.
OrQuery::eval
An OrQuery
represents the union of the results for its two operands, which we obtain by calling eval
on each of its operands. Because these operands are Query
objects, calling eval
is a call to Query::eval
, which in turn makes a virtual call to eval
on the underlying Query_base
object. Each of these calls yields a QueryResult
representing the line numbers in which its operand appears. We’ll combine those line numbers into a new 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
.
The eval
function ends by building and returning a QueryResult
representing the combined match. The QueryResult
constructor (§12.3.2, p. 489) takes three arguments: a string
representing the query, a shared_ptr
to the set
of matching line numbers, and a shared_ptr
to the vector
that represents the input file. We call rep
to generate the string
and get_file
to obtain the shared_ptr
to the file. Because both left
and right
refer to the same file, it doesn’t matter which of these we use for get_file
.
AndQuery::eval
The AndQuery
version of eval
is similar to the OrQuery
version, except that it calls a library algorithm to find the lines in common to both queries:
// returns the intersection of its operands' result sets
QueryResult
AndQuery::eval(const TextQuery& text) const
{
// virtual calls through the Query operands to get result sets for the operands
auto left = lhs.eval(text), right = rhs.eval(text);
// set to hold the intersection of left and right
auto ret_lines = make_shared<set<line_no>>();
// writes the intersection of two ranges to a destination iterator
// destination iterator in this call adds elements to ret
set_intersection(left.begin(), left.end(),
right.begin(), right.end(),
inserter(*ret_lines, ret_lines->begin()));
return QueryResult(rep(), ret_lines, left.get_file());
}
Here we use the library set_intersection
algorithm, which is described in Appendix A.2.8 (p. 880), to merge these two set
s.
The set_intersection
algorithm takes five iterators. It uses the first four to denote two input sequences (§10.5.2, p. 413). Its last argument denotes a destination. The algorithm writes the elements that appear in both input sequences into the destination.
In this call we pass an insert iterator (§10.4.1, p. 401) as the destination. When set_intersection
writes to this iterator, the effect will be to insert a new element into ret_lines
.
Like the OrQuery eval
function, this one ends by building and returning a QueryResult
representing the combined match.
NotQuery::eval
NotQuery
finds each line of the text within which the operand is not found:
// returns the lines not in its operand's result set
QueryResult
NotQuery::eval(const TextQuery& text) const
{
// virtual call to eval through the Query operand
auto result = query.eval(text);
// start out with an empty result set
auto ret_lines = make_shared<set<line_no>>();
// we have to iterate through the lines on which our operand appears
auto beg = result.begin(), end = result.end();
// for each line in the input file, if that line is not in result,
// add that line number to ret_lines
auto sz = result.get_file()->size();
for (size_t n = 0; n != sz; ++n) {
// if we haven't processed all the lines in result
// check whether this line is present
if (beg == end || *beg != n)
ret_lines->insert(n); // if not in result, add this line
else if (beg != end)
++beg; // otherwise get the next line number in result if there is one
}
return QueryResult(rep(), ret_lines, result.get_file());
}
As in the other eval
functions, we start by calling eval
on this object’s operand. That call returns the QueryResult
containing the line numbers on which the operand appears, but we want the line numbers on which the operand does not appear. That is, we want every line in the file that is not already in result
.
We generate that set
by iterating through sequenital integers up to the size of the input file. We’ll put each number that is not in result
into ret_lines
. We position beg
and end
to denote the first and one past the last elements in result
. That object is a set
, so when we iterate through it, we’ll obtain the line numbers in ascending order.
The loop body checks whether the current number is in result
. If not, we add that number to ret_lines
. If the number is in result
, we increment beg
, which is our iterator into result
.
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.
Exercise 15.39: Implement the Query
and Query_base
classes. Test your application by evaluating and printing a query such as the one in Figure 15.3 (p. 638).
Exercise 15.40: In the OrQuery eval
function what would happen if its rhs
member returned an empty set? What if its lhs
member did so? What if both rhs
and lhs
returned empty sets?
Exercise 15.41: Reimplement your classes to use built-in pointers to Query_base
rather than shared_ptr
s. Remember that your classes will no longer be able to use the synthesized copy-control members.
Exercise 15.42: Design and implement one of the following enhancements:
(a) Print words only once per sentence rather than once per line.
(b) Introduce a history system in which the user can refer to a previous query by number, possibly adding to it or combining it with another.
(c) Allow the user to limit the results so that only matches in a given range of lines are displayed.