15.9. Возвращаясь к запросам текста.

В качестве последнего примера наследования дополним приложение текстового запроса из раздела 12.3. Написанные в этом разделе классы позволят искать вхождения данного слова в файле. Дополним эту систему возможностью создавать более сложные запросы. В этих примерах запросы будут выполняться к тексту следующей истории:

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?"

Система должна поддерживать следующие запросы.

• Запросы слов находят все строки, соответствующие заданной строке:

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?"

• Инверсный запрос с использованием оператора ~ возвращает строки, которые не содержат заданную строку:

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.

...

• Запросы ИЛИ с использованием оператора | возвращают строки, содержащие любую из двух заданных строк:

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,

• Запросы И с использованием оператора & возвращают строки, содержащие обе заданные строки:

Executing query for: (hair & Alice)

(hair & Alice) occurs 1 time

(line 1) Alice Emma has long flowing red hair.

Кроме того, нужна возможность объединить эти операторы так.

fiery & bird | wind

Для обработки составных выражений, таких как в этом примере, будут использованы обычные правила приоритета С++ (см. раздел 4.1.2). Таким образом, этому запросу соответствует строка, в которой присутствуют слова fiery и bird или слово wind:

Executing Query for: ((fiery & bird) | wind)

((fiery & bird) | wind) occurs 3 times

(line 2) Her Daddy says when the wind blows

(line 4) like a fiery bird in flight.

(line 5) A beautiful fiery bird, he tells her,

В отображаемом результате для указания способа интерпретации запроса используются круглые скобки. Подобно первоначальной реализации, система не должна отображать одинаковые строки несколько раз.

15.9.1. Объектно-ориентированное решение.

Для представления запросов на поиск слов вполне логично было бы использовать класс TextQuery (см. раздел 12.3.2), а другие классы запросов можно было бы получить как производные от этого класса.

Однако такой подход неверен. Концептуально инверсный запрос не является разновидностью запроса на поиск слова. Инверсный запрос — это скорее запрос типа "имеет" (запрос на поиск слова или любой другой тип запроса), результат которого интерпретируется негативно.

Исходя из этого можно сделать вывод, что разные виды запросов следует оформить как независимые классы, которые совместно используют общий базовый класс:

WordQuery // Daddy

NotQuery  // ~Alice

OrQuery   // hair | Alice

AndQuery  // hair & Alice

Эти классы будет иметь только две функции.

• Функция eval(), получающая объект класса TextQuery и возвращающая объект класса QueryResult. Для поиска запрошенной строки функция eval() будет использовать переданный объект класса TextQuery.

• Функция rep(), возвращающая строковое представление базового запроса. Эту функцию использует функция eval() для создания объекта класса QueryResult, представляющего соответствия, а также оператор вывода, отображающий выражение запроса.

Абстрактный базовый класс.

Как уже упоминалось, все четыре типа запроса не связаны друг с другом наследованием; концептуально они элементы одного уровня. Каждый класс использует тот же интерфейс, а значит, для представления этого интерфейса следует определить абстрактный базовый класс (см. раздел 15.4). Назовем этот абстрактный базовый класс Query_base, поскольку он должен служить корневым классом иерархии запроса.

Ключевая концепция. Наследование или композиция. Проектирование иерархии наследования — это достаточно сложная тема, которая выходит за рамки данного вводного курса. Однако имеет смысл упомянуть об одном достаточно важном факторе проектирования, с которым должен быть знаком каждый программист. При определении класса как открыто производного от другого производный и базовый классы реализуют взаимоотношения типа "является" (is а). В хорошо проработанных иерархиях объекты открыто унаследованных классов применимы везде, где ожидается объект базового класса. Еще одним популярным способом взаимоотношений классов является принцип "имеет" (has а). Типы, связанные отношениями "имеет", подразумевают принадлежность. В рассматриваемом примере с книжным магазином базовый класс представляет концепцию книги, продаваемой по предусмотренной цене, а класс Bulk_quote "является" конкретной книгой, продаваемой по розничной цене с определенной стратегией скидок. Классы приложения книжного магазина "имеют" цену и ISBN.

Класс Query_base определит функции eval() и rep() как чистые виртуальные (см. раздел 15.4). Каждый из классов, представляющих специфический вид запроса, должен переопределить эти функции. Классы WordQuery и NotQuery унаследуем непосредственно от класса Query_base. У классов AndQuery и OrQuery будет одна общая особенность, которой не будет у остальных классов в системе: у каждого будет по два операнда. Для моделирования этой особенности определим другой абстрактный базовый класс, BinaryQuery, представляющий запросы с двумя операндами. Классы AndQuery и OrQuery наследуются от класса BinaryQuery, который в свою очередь наследуется от класса Query_base. Результатом этих решений будет проект классов, представленный на рис. 15.2.

Рис. 15.2. Иерархия наследования Query_base.

Сокрытие иерархии в классе интерфейса.

Рассматриваемая программа будет отрабатывать запросы, а не создавать их. Но чтобы запустить программу на выполнение, необходимо определить способ создания запроса. Проще всего сделать это непосредственно в коде при помощи выражения С++. Например, чтобы создать описанный ранее составной запрос, можно использовать следующий код:

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

Это довольно сложное описание неявно предполагает, что код пользовательского уровня не будет использовать унаследованные классы непосредственно. Вместо этого будет создан класс интерфейса по имени Query (Запрос), который и скроет иерархию. Класс Query будет хранить указатель на класс Query_base. Этот указатель будет связан с объектом типа, производного от класса Query_base. Класс Query будет предоставлять те же функции, что и классы Query_base: функцию eval() для обработки соответствующего запроса и функцию rep() для создания строковой версии запроса. В нем также будет определен перегруженный оператор вывода, чтобы отображать соответствующий запрос.

Пользователи будут создавать объекты класса Query_base и работать с ними только косвенно, через функции объектов класса Query. Для класса Query, наряду с получающим строку конструктором, определим три перегруженных оператора. Каждая из этих функций будет динамически резервировать новый объект типа, производного от класса Query_base:

• Оператор  & создает объект класса Query, связанный с новым объектом класса AndQuery.

• Оператор  | создает объект класса Query, связанный с новым объектом класса OrQuery.

• Оператор  ~ создает объект класса Query, связанный с новым объектом класса NotQuery.

• Конструктор класса Query, получающий строку и создающий новый объект класса WordQuery.

Как работают эти классы.

Следует понять, что работа этого приложения состоит в основном из построения объектов для представления запросов пользователя. Например, приведенное выше выражение создает коллекцию взаимодействовавших объектов, представленных на рис. 15.3.

Рис. 15.3. Объекты, созданные выражениями запросов.

Как только создано дерево объектов, обработка (или отображение) данного запроса сводится к простому процессу (осуществляемому компилятором), который, следуя по линиям, опрашивает каждый объект дерева, чтобы выполнить (или отобразить) необходимые действия. Например, если происходит вызов функции eval() объекта q (т.е. корневого класса дерева), функция eval() опросит объект класса OrQuery, на который он указывает. Обработка этого объекта класса OrQuery приведет к вызову функции eval() для двух его операндов, что, в свою очередь, приведет к вызову функции eval() для объектов классов AndQuery и WordQuery, которые осуществляют поиск слова wind. Обработка объекта класса AndQuery, в свою очередь, приведет к обработке двух его объектов класса WordQuery, создав результаты для слов fiery и bird соответственно.

Новичкам в объектно-ориентированном программировании зачастую трудней всего разобраться в проекте программы. Но как только проект станет абсолютно понятен, его реализация не вызывает проблем. Чтобы проще было понять суть проекта, все используемые в этом примере классы были обобщены в табл. 15.1.

Таблица 15.1. Обзор проекта программы

Классы и операторы интерфейса программы запросов
TextQuery	Класс, который читает указанный файл и создает карту поиска. Этот класс предоставляет функцию поиска query(), которая получает строковый аргумент и возвращает объект класса QueryResult, представляющий строки, в которых присутствует ее аргумент (см. раздел 12.3.2)
QueryResult	Класс, содержащий результаты вызова функции query() (см. раздел 12.3.2)
Query	Класс интерфейса, указывающий на объект типа, производного от класса Query_base
Query q(s)	Связывает объект q класса Query с новым объектом класса WordQuery, содержащим строку s
q1 & q2	Возвращает объект класса Query, связанный с новым объектом класса AndQuery, который содержит объекты q1 и q2
q1 | q2	Возвращает объект класса Query, связанный с новым объектом класса OrQuery, содержащим объекты q1 и q2
~q	Возвращает объект класса Query, связанный с новым объектом класса NotQuery, содержащим объект q
Классы реализации программы запросов
Query_base	Абстрактный класс, базовый для классов запроса
WordQuery	Класс, производный от класса Query_base, который ищет указанное слово
NotQuery	Класс, производный от класса Query_base, представляющий набор строк, в которых указанный операнд Query отсутствует
BinaryQuery	Абстрактный базовый класс, производный от класса Query_base, который представляет запросы с двумя операндами типа Query
OrQuery	Класс, производный от класса BinaryQuery, который возвращает набор номеров строк, в которых присутствует хотя бы один из операндов
AndQuery	Класс, производный от класса BinaryQuery, который возвращает набор номеров строк, в которых присутствуют оба операнда

Упражнения раздела 15.9.1.

Упражнение 15.31. При условии, что s1, s2, s3 и s4 являются строками укажите, какие объекты создаются в следующих выражениях:

(a) Query(s1) | Query(s2) & ~ Query(s3);

(b) Query(s1) | (Query(s2) & ~ Query(s3));

(c) (Query(s1) & (Query(s2)) | (Query(s3) & Query(s4)));

15.9.2. Классы Query_base и Query.

Начнем реализацию с определения класса Query_base:

// абстрактный класс, являющийся базовым для конкретных типов запроса;

// все члены закрыты

class Query_base {

 friend class Query;

protected:

 using line_no = TextQuery::line_no; // используется в функциях eval()

 virtual ~Query_base() = default;

private:

 // eval() возвращает соответствующий запросу QueryResult

 virtual QueryResult eval(const TextQuery&) const = 0;

 // rep() строковое представление запроса

 virtual std::string rep() const = 0;

};

Обе функции, eval() и rep(), являются чистыми виртуальными, что делает класс Query_base абстрактным базовым (см. раздел 15.4). Поскольку класс Query_base не предназначен для пользователей и непосредственного использования в производных классах, у него нет открытых членов. Класс Query_base будет использоваться только через объекты класса Query. Класс предоставляет дружественные отношения классу Query, поскольку его члены вызывают виртуальные функции класса Query_base.

Защищенный член line_no будет использоваться в функциях eval(). Деструктор также будет защищен, поскольку он используется (неявно) деструкторами в производных классах.

Класс Query.

Класс Query предоставляет интерфейс к иерархии наследования Query_base и скрывает ее. Каждый объект класса Query содержит указатель shared_ptr на соответствующий объект класса Query_base. Поскольку класс Query — единственный интерфейс к классам иерархии Query_base, он должен определить собственные версии функций eval() и rep().

Конструктор Query(), получающий строку, создаст новый объект класса WordQuery и свяжет его указатель-член shared_ptr с этим недавно созданным объектом. Операторы &, | и ~ создают объекты AndQuery, OrQuery и NotQuery соответственно. Эти операторы возвращают объект класса Query, связанный с созданным им объектом. Для поддержки этих операторов класс Query нуждается в конструкторе, получающем указатель shared_ptr на класс Query_base и сохраняющем его. Сделаем этот конструктор закрытым, поскольку объекты класса Query_base не предназначены для определения общим пользовательским кодом. Так как этот конструктор является закрытым, операторы следует сделать дружественными.

Исходя из приведенного выше проекта, сам класс Query довольно прост:

// класс интерфейса для взаимодействия с иерархией

// наследования Query_base

class Query {

 // эти операторы должны обращаться к указателю shared_ptr

 friend Query operator~(const Query &);

 friend Query operator|(const Query&, const Query&);

 friend Query operator&(const Query&, const Query&);

public:

 Query(const std::string&); // создает новый WordQuery

 // функции интерфейса: вызывают соответствующий оператор Query_base

 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;

};

Начнем с объявления дружественных операторов, создающих объекты класса Query. Эти операторы должны быть друзьями, чтобы использовать закрытый конструктор.

В открытом интерфейсе для класса Query объявляется, но еще не может быть определен получающий строку конструктор. Этот конструктор создает объект класса WordQuery, поэтому невозможно определить этот конструктор, пока не определен сам класс WordQuery.

Два других открытых члена представляют интерфейс для класса Query_base. В каждом случае оператор класса Query использует свой указатель класса Query_base для вызова соответствующей (виртуальный) функции класса Query_base. Фактически вызываемая версия определяется во время выполнения и будет зависеть от типа объекта, на который указывает указатель q.

Оператор вывода класса Query.

Оператор вывода — хороший пример того, как работает вся система запросов:

std::ostream &

operator<<(std::ostream &os, const Query &query) {

 // Query::rep() осуществляет виртуальный вызов через свой

 // указатель Query_base на rep()

 return os << query.rep();

}

При выводе объекта класса Query оператор вывода вызывает (открытую) функцию-член rep() класса Query. Эта функция осуществляет виртуальный вызов через свой указатель-член функции-члена rep() объекта, на который указывает данный объект класса Query.

Query andq = Query(sought1) & Query(sought2);

cout << andq << endl;

Таким образом, когда в коде встречается оператор вывода, он вызывает функцию Query::rep() объекта andq. Функция Query::rep() в свою очередь осуществляет виртуальный вызов через свой указатель класса Query_base на версию функции rep() класса Query_base. Поскольку объект andq указывает на объект класса AndQuery, этот вызов выполнит функцию AndQuery::rep().

Упражнения раздела 15.9.2.

Упражнение 15.32. Что будет при копировании, перемещении, присвоении и удалении объекта класса Query?

Упражнение 15.33. А объектов класса Query_base?

15.9.3. Производные классы.

Самая интересная часть классов, производных от класса Query_base, в том, как они представляются. Класс WordQuery проще всех. Его задача — хранение искомого слова.

Другие классы работают на одном или двух операндах. У класса NotQuery один операнд, а у классов AndQuery и OrQuery — по два. Операндами в каждом из этих классов могут быть объекты любого из реальных классов, производных от класса Query_base: NotQuery может быть применен к WordQuery, как и AndQuery, OrQuery или NotQuery. Для обеспечения такой гибкости операнды следует хранить как указатели на класс Query_base. Таким образом, можно привязать указатель на любой необходимый реальный класс.

Но вместо того, чтобы хранить указатель на класс Query_base, классы будут сами использовать объект Query. Подобно тому, как пользовательский код упрощается при использовании класса интерфейса, можно упростить код собственного класса, используя тот же класс.

Теперь, когда конструкция этих классов известна, их можно реализовать.

Класс WordQuery.

Класс WordQuery отвечает за поиск заданной строки. Это единственная операция, которая фактически выполняет запрос для данного объекта класса TextQuery:

class WordQuery: public Query_base {

 friend class Query; // Query использует конструктор WordQuery

 WordQuery(const std::string &s) : query_word (s) { }

 // конкретный класс: WordQuery определяет все унаследованные чистые

 // виртуальные функции

 QueryResult eval(const TextQuery &t) const

  { return t.query(query_word); }

 std::string rep() const { return query_word; }

 std::string query_word; // искомое слово

};

Подобно классу Query_base, у класса WordQuery нет открытых членов; он должен сделать класс Query дружественным, чтобы позволить ему получать доступ к конструктору WordQuery().

Каждый из конкретных классов запроса должен определить унаследованные чистые виртуальные функции eval() и rep(). Обе функции определены в теле класса WordQuery: функция eval() вызывает функцию-член query() своего параметра типа TextQuery, который фактически осуществляет поиск в файле; функция rep() возвращает строку, которую данный объект класса WordQuery представляет (т.е. query_word).

Определив класс WordQuery, можно определить конструктор Query(), получающий строку:

inline

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

Этот конструктор резервирует объект класса WordQuery и инициализирует его указатель-член так, чтобы он указывал на этот недавно созданный объект.

Класс NotQuery и оператор ~

Оператор ~ подразумевает создание объекта класса NotQuery, содержащего инверсный запрос:

class NotQuery: public Query_base {

 friend Query operator~(const Query &);

 NotQuery(const Query &q): query(q) { }

 // конкретный класс: NotQuery определяет все унаследованные

 // чистые виртуальные функции

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

}

Поскольку все члены класса NotQuery являются закрытыми, объявляем оператор  ~ дружественным. Чтобы отобразить объект класса NotQuery, следует вывести символ " ~" сопровождаемый основным запросом. Чтобы сделать приоритет очевидным для читателя, заключим запрос в скобки.

Следует заметить то, что вызов функции rep() объекта класса NotQuery в конечном счете приводит к виртуальному вызову функции собственной функции-члена rep(): query.rep() — это невиртуальный вызов функции-члена rep() класса Query. Функция Query::rep() в свою очередь осуществляет вызов q->rep(), являющийся виртуальным вызовом через указатель Query_base.

Оператор  ~ динамически резервирует новый объект класса NotQuery. Оператор return (неявно) использует конструктор Query(), получающий указатель shared_ptr<Query_base>. Таким образом, оператор return эквивалентен следующему:

// резервировать новый объект NotQuery

// связать новый объект NotQuery с указателем shared_ptr<Query_base>

shared_ptr<Query_base> tmp(new NotQuery(expr));

return Query(tmp); // использовать конструктор Query(), получающий

                   // указатель shared_ptr

Функция-член eval() достаточно сложна, поэтому реализуем ее вне тела класса. Более подробно функция eval() рассматривается в разделе 15.9.4.

Класс BinaryQuery.

Класс BinaryQuery — это абстрактный базовый класс, содержащий данные, необходимые двум классам запроса, AndQuery и OrQuery, которые используют по два операнда:

class BinaryQuery: public Query_base {

protected:

 BinaryQuery(const Query &l, const Query &r, std::string s):

  lhs(l), rhs(r), opSym(s) { }

 // абстрактный класс: BinaryQuery функцию eval() не определяет

 std::string rep() const { return "(" + lhs.rep() + " "

                                      + opSym + " "

                                      + rhs.rep() + ")"; }

 Query lhs, rhs;    // правый и левый операнды

 std::string opSym; // имя оператора

};

Данными класса BinaryQuery являются два операнда запроса и символ оператора. Конструктор получает эти два операнда и символ оператора, каждый из которых он хранит в соответствующих переменных-членах.

Чтобы отобразить объект класса BinaryOperator, следует вывести выражение в скобках, состоящее из левого операнда, оператора и правого операнда. Как и в случае класса NotQuery, вызов функции rep() в конечном счете осуществляет вызов виртуальных функций rep() объектов класса Query_base, на которые указывают параметры lhs и rhs.

Класс BinaryQuery не переопределяет функцию eval(), а следовательно, наследует ее чистой виртуальной. Таким образом, класс BinaryQuery остается абстрактным и его объекты создавать нельзя.

Классы AndQuery, OrQuery и их операторы.

Классы AndQuery и OrQuery, а также соответствующие им операторы очень похожи:

class AndQuery: public BinaryQuery {

 friend Query operators(const Query&, const Query&);

 AndQuery(const Query &left, const Query &right):

  BinaryQuery(left, right, "&") { }

 // конкретный класс: AndQuery наследует функцию rep(),

 // а остальные чистые виртуальные функции переопределяет

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

}

Эти классы объявляют соответствующий оператор дружественным и определяют конструктор, создающий их базовую часть класса BinaryQuery с соответствующим оператором. Они наследуют определение функции rep() от класса BinaryQuery, но каждый из них определяет собственную версию функции eval().

Как и оператор операторы & и | возвращают указатель shared_ptr на вновь созданный объект соответствующего типа. Этот указатель shared_ptr приводится к типу Query в операторе return каждого из этих операторов.

Упражнения раздела 15.9.3.

Упражнение 15.34. Исходя из выражения, представленного на рис. 15.3:

(a) Перечислите конструкторы, задействованные при обработке этого выражения;

(b) Перечислите обращения к функции rep() из выражения cout << q;

(c) Перечислите обращения к функции eval() из выражения q.eval.

Упражнение 15.35. Реализуйте классы Query и Query_base, включая определение функции rep(), но исключая определение функции eval().

Упражнение 15.36. Добавьте операторы вывода в конструкторы и функции-члены rep(). Запустите код на выполнение, чтобы проверить свои ответы на вопросы (а) и (b) первого упражнения.

Упражнение 15.37. Какие изменения следовало бы внести в классы, если бы у производных классов были члены типа shared_ptr<Query_base>, а не типа Query?

Упражнение 15.38. Допустимы ли следующие объявления? Если нет, то почему? Если да, то что они означают?

BinaryQuery а = Query("fiery") & Query("bird");

AndQuery b = Query("fiery") & Query("bird");

OrQuery с = Query("fiery") & Query("bird");

15.9.4. Виртуальные функции eval().

Функции eval() — основа системы запросов. Каждая из них вызывает функцию eval() своего операнда (операндов), а затем применяет собственную логику вычислений: функция eval() класса OrQuery возвращает объединение результатов своих операндов, а функция eval() класса AndQuery возвращает их пересечение. Функция eval() класса NotQuery немного сложней: она должна возвращать номера строк, не входящих в набор операнда.

Для обеспечения обработки в функциях eval() необходимо использовать ту версию класса QueryResult, в который определены члены, добавленные в упражнениях раздела 12.3.2. Подразумевается, что у класса QueryResult есть функции-члены begin() и end(), позволяющие перебрать набор номеров строк, которые содержит объект класса QueryResult. Подразумевается также, что у класса QueryResult есть функция-член get_file(), возвращающая указатель shared_ptr на файл, к которому осуществляется запрос.

Класс Query использует функции-члены begin() и end(), определенные для класса QueryResult в упражнении 12.3.2.

Функция OrQuery::eval().

Функция eval() класса OrQuery объединяет наборы номеров строк, возвращенных его операндами, т.е. ее результатом является объединение результатов двух операндов.

Объект класса OrQuery представляет объединение результатов двух своих операндов, полученных при вызове функции-члена eval() каждого из них. Поскольку эти операнды являются объектами класса Query, вызов функции eval() является вызовом Query::eval(), который в свою очередь осуществляет виртуальный вызов функции eval() объекта базового класса Query_base. Каждый из этих вызовов возвращает объект класса QueryResult, представляющий номера строк, в которых присутствует его операнд. Эти номера строк объединяются в новый набор:

// возвращает объединение наборов результатов своих операндов

QueryResult

OrQuery::eval(const TextQuery& text) const {

 // виртуальные вызовы через члены Query, lhs и rhs

 // вызовы eval() возвращают QueryResult для каждого операнда

 auto right = rhs.eval(text), left = lhs.eval(text);

 // копировать номера строк левого операнда в результирующий набор

 auto ret_lines =

  make_shared<set<line_no>>(left.begin(), left.end());

 // вставить строки из правого операнда

 ret_lines->insert(right.begin(), right.end());

 // возвратить новый QueryResult, представляющий объединение lhs и rhs

 return QueryResult(rep(), ret_lines, left.get_file());

}

Набор ret_lines инициализируется с использования того конструктора, который получает пару итераторов. Функции-члены begin() и end() класса QueryResult возвращают итераторы на номера строк набора. Таким образом, набор ret_lines создается при копировании элементов из набора left. Затем для вставки элементов из набора right вызывается функция insert(). После этого вызова набор ret_lines содержит номера строк из наборов, которые присутствуют в наборах left или right.

Функция eval() завершает работу, создавая и возвращая объект класса QueryResult, представляющий объединение соответствий. Конструктор QueryResult() (см. раздел 12.3.2) получает три аргумента: строку, представляющую запрос, указатель shared_ptr на набор соответствующих номеров строк и указатель shared_ptr на вектор, представляющий входной файл. Вызов функции rep() позволяет создать строку, а вызов функции get_file() — получить указатель shared_ptr на файл. Поскольку оба набора, left и right, относятся к тому же файлу, не имеет значения, который из них использовать для функции get_file().

Функция AndQuery::eval().

Версия функции eval() класса AndQuery подобна версии класса OrQuery, за исключением того, что она использует библиотечный алгоритм для поиска строк, общих для обоих запросов:

// возвращает пересечение наборов результатов своих операндов

QueryResult

AndQuery::eval(const TextQuery& text) const {

 // виртуальный вызов через операнды класса Query для получения

 // результирующих наборов для операндов

 auto left = lhs.eval(text), right = rhs.eval(text);

 // набор для хранения пересечения left и right

 auto ret_lines = make_shared<set<line_no>>();

 // выводит пересечение двух диапазонов в итератор назначения

 // итератор назначения в этом вызове добавляет элементы в 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());

}

Здесь для объединения двух наборов используется библиотечный алгоритм set_intersection, описанный в приложении А.2.8.

Алгоритм set_intersection получает пять итераторов. Первые четыре он использует для обозначения двух исходных последовательностей (см. раздел 10.5.2). Его последний аргумент обозначает получателя. Алгоритм выводит элементы, присутствующие в обеих исходных последовательностях, в результирующую.

В данном вызове получателем является итератор вставки (см. раздел 10.4.1). Результатом записи алгоритмом set_intersection в этот итератор будет вставка нового элемента в набор ret_lines.

Подобно функции eval() класса OrQuery, эта завершается созданием и возвращением объекта класса QueryResult, представляющего объединение соответствий.

Функция NotQuery::eval().

Функция eval() класса NotQuery ищет в тексте все строки, в которых операнд отсутствует.

// возвращает строки, отсутствующие в наборе результатов

// операнда QueryResult

NotQuery::eval(const TextQuery& text) const {

 // виртуальный вызов для вычисления операнда Query

 auto result = query.eval(text);

 // начать с пустого результирующего набора данных

 auto ret_lines = make_shared<set<line_no>>();

 // следует перебрать строки, в которых присутствует операнд

 auto beg = result.begin(), end = result.end();

 // для каждой строки во входном файле, если она отсутствует

 // в result, добавить ее номер в ret_lines

 auto sz = result.get_file()->size();

 for (size_t n = 0; n != sz; ++n) {

  // если не обработаны все строки в result

  // проверить присутствие этой строки

  if (beg == end || *beg != n)

   ret_lines->insert(n); // если нет в result, добавить строку

  else if (beg != end)

   ++beg; // в противном случае получить следующий номер строки

          // в result, если она есть

 }

 return QueryResult(rep(), ret_lines, result.get_file());

}

Как и другие функции eval(), данная начинается с вызова функции eval() операнда объекта. Этот вызов возвращает объект класса QueryResult, содержащий номера строк, в которых присутствует операнд. Однако вернуть необходимо набор номеров строк, в которых операнд отсутствует. Как и в других функциях eval(), данная начинается с вызова функции eval() операнда объекта. Вызов возвращает объект класса QueryResult, содержащий номера строк, в которых операнд присутствует, но необходимы номера строки, на которых операнд отсутствует. Поэтому следует найти в файле все строки, отсутствующие в наборе результатов.

Набор создается в результате последовательного перебора целых чисел до размера входного файла. Каждое число, отсутствующее в наборе result, помещается в набор ret_lines. Итераторы beg и end устанавливаются на первый и следующий после последнего элементы в наборе result. Поскольку речь идет о наборе, при переборе номера строк будут следовать в порядке возрастания.

Тело цикла проверяет наличие текущего числа в наборе result. Если его нет, то число добавляется в набор ret_lines. Если он есть, осуществляется приращение итератора beg набора result.

Как только все номера строк будут обработаны, возвращается объект класса QueryResult, содержащий набор ret_lines наряду с результатами выполнения функций rep() и get_file(), как и у предыдущих функций eval().

Упражнения раздела 15.9.4.

Упражнение 15.39. Реализуйте классы Query и Query_base. Проверьте приложение на вычислении и выводе запроса, представленного на рис. 15.3.

Упражнение 15.40. Что будет, если параметр rhs функции-члена eval() класса OrQuery возвратит пустой набор? Что, если так поступит ее параметр lhs? Что если и rhs, и lhs возвратят пустые множества?

Упражнение 15.41. Переделайте свои классы так, чтобы использовать встроенные указатели на класс Query_base, а не интеллектуальные указатели shared_ptr. Помните, что ваши классы больше не смогут использовать синтезируемые функции-члены управления копированием.

Упражнение 15.42. Разработайте и реализуйте одно из следующих дополнений.

(a) Организуйте вывод слов только однажды в предложении, а не однажды в строке.

(b) Снабдите систему историей, позволяющей пользователю обратиться к предыдущему запросу по номеру, а также добавлять или комбинировать их с другими.

(c) Позвольте пользователю ограничивать результаты так, чтобы отображался набор соответствий только в заданном диапазоне строк.