Виртуальная функция eval()
В основе иерархии классов Query лежит виртуальная функция eval() (но с точки зрения возможностей языка она наименее интересна). Как и для других функций-членов, разумной реализации eval() в абстрактном классе Query нет, поэтому мы объявляем ее чисто виртуальной:
class Query {
public:
virtual void eval() = 0;
// ...
};
Реальное разрешение имени eval() происходит при построении отображения слов на вектор позиций. Если слово есть в тексте, то в отображении будет его вектор позиций. В нашей реализации вектор позиций, если он имеется, передается конструктору NameQuery вместе с самим словом. Поэтому в классе NameQuery функция eval() пуста.
Однако мы не можем унаследовать чисто виртуальную функцию из Query. Почему? Потому что NameQuery– это конкретный класс, объекты которого разрешается создавать в приложении. Если бы мы унаследовали чисто виртуальную функцию, то он стал бы абстрактным классом, так что создать объект такого типа не удалось бы. Поэтому мы объявим eval() пустой функцией:
class NameQuery : public Query {
public:
virtual void eval() {}
// ...
};
Для запроса NotQuery отыскиваются все строки текста, где указанное слово отсутствует. Для таких строк в член _loc класса NotQuery помещаются все пары (строка, колонка). Наша реализация выглядит следующим образом:
void NotQuery::eval()
{
// вычислим операнд
_op->eval();
// _all_locs - это вектор, содержащий начальные позиции всех слов,
// он является статическим членом NotQuery:
// static const vector<locations>* _all_locs
vector< location >::const_iterator
iter = _all_locs->begin(),
iter_end = _all_locs->end();
// получить множество строк, в которых операнд встречается
set<short> *ps = _vec2set( _op->locations() );
// для каждой строки, где операнд не найден,
// скопировать все позиции в _loc
for ( ; iter != iter_end; ++iter )
{
if ( ! ps->count( (*iter).first )) {
_loc.push_back( *iter );
}
}
}
Ниже приводится трассировка выполнения запроса NotQuery. Операнд встречается в 0, 3 и 5 строках текста. (Напомним, что внутри программы строки текста в векторе нумеруются с 0; а когда мы предъявляем строки пользователю, мы нумеруем их с единицы.) Поэтому при вычислении ответа создается вектор, содержащий начальные позиции слов в строках 1,2 и 4. (Мы отредактировали вектор позиций, чтобы он занимал меньше места.)
==> ! daddy
daddy ( 3 ) lines match
display_location_vector:
first: 0 second: 8
first: 3 second: 3
first: 5 second: 5
! daddy ( 3 ) lines match
display_location_vector:
first: 1 second: 0
first: 1 second: 1
first: 1 second: 2
...
first: 1 second: 10
first: 2 second: 0
first: 2 second: 1
...
first: 2 second: 12
first: 4 second: 0
first: 4 second: 1
...
first: 4 second: 12
Requested query: ! daddy
( 2 ) when the wind blows through her hair, it looks almost alive,
( 3 ) like a fiery bird in flight. A beautiful fiery bird, he tells her,
( 5 ) she tells him, at the same time wanting him to tell her more.
При обработке запроса OrQuery векторы позиций обоих операндов объединяются. Для этого применяется обобщенный алгоритм merge(). Чтобы merge() мог упорядочить пары (строка, колонка), мы определяем объект-функцию для их сравнения. Ниже приведена наша реализация:
class less_than_pair {
public:
bool operator()( location loc1, location loc2 )
{
return (( loc1.first < loc2.first ) ||
( loc1.first == loc2.first ) &&
( loc1.second < loc2.second ));
}
};
void OrQuery::eval()
{
// вычислить левый и правый операнды
_lop->eval();
_rop->eval();
// подготовиться к объединению двух векторов позиций
vector< location, allocator >::const_iterator
riter = _rop->locations()->begin(),
liter = _lop->locations()->begin(),
riter_end = _rop->locations()->end(),
liter_end = _lop->locations()->end();
merge( liter, liter_end, riter, riter_end,
inserter( _loc, _loc.begin() ),
less_than_pair() );
}
А вот трассировка выполнения запроса OrQuery, в которой мы выводим вектор позиций каждого из двух операндов и результат их объединения. (Напомним еще раз, что для пользователя строки нумеруются с 1, а внутри программы – с 0.)
==> fiery || untamed
fiery ( 1 ) lines match
display_location vector:
first: 2 second: 2
first: 2 second: 8
untamed ( 1 ) lines match
display_location vector:
first: 3 second: 2
fiery || untamed ( 2 ) lines match
display_location vector:
first: 2 second: 2
first: 2 second: 8
first: 3 second: 2
Requested query: fiery || untamed
( 3 ) like a fiery bird in flight. A beautiful fiery bird, he tells her,
( 4 ) magical but untamed. "Daddy, shush, there is no such thing,"
При обработке запроса AndQuery мы обходим векторы позиций обоих операндов и ищем соседние слова. Каждая найденная пара вставляется в вектор _loc. Основная трудность связана с тем, что эти векторы нужно просматривать синхронно, чтобы можно было установить соседство слов.
void AndQuery::eval()
{
// вычислить левый и правый операнды
_lop->eval();
_rop->eval();
// установить итераторы
vector< location, allocator >::const_iterator
riter = _rop->locations()->begin(),
liter = _lop->locations()->begin(),
riter_end = _rop->locations()->end(),
liter_end = _lop->locations()->end();
// продолжать цикл, пока есть что сравнивать
while ( liter != liter_end &&
riter != riter_end )
{
// пока номер строки в левом векторе больше, чем в правом
while ( (*liter).first > (*riter).first )
{
++riter;
if ( riter == riter_end ) return;
}
// пока номер строки в левом векторе меньше, чем в правом
while ( (*liter).first < (*riter).first )
{
// если соответствие найдено для последнего слова
// в одной строке и первого слова в следующей
// _max_col идентифицирует последнее слово в строке
if ( ((*liter).first == (*riter).first-1 ) &&
((*riter).second == 0 ) &&
((*liter).second == (*_max_col)[ (*liter).first ] ))
{
_loc.push_back( *liter );
_loc.push_back( *riter );
++riter;
if ( riter == riter_end ) return;
}
++liter;
if ( liter == liter_end ) return;
}
// пока оба в одной и той же строке
while ( (*liter).first == (*riter).first )
{
if ( (*liter).second+1 == ((*riter).second) )
{ // соседние слова
_loc.push_back( *liter ); ++liter;
_loc.push_back( *riter ); ++riter;
}
else
if ( (*liter).second <= (*riter).second )
++liter;
else ++riter;
if ( liter == liter_end || riter == riter_end )
return;
}
}
}
А так выглядит трассировка выполнения запроса AndQuery, в которой мы выводим векторы позиций обоих операндов и результирующий вектор:
==> fiery && bird
fiery ( 1 ) lines match
display_location vector:
first: 2 second: 2
first: 2 second: 8
bird ( 1 ) lines match
display_location vector:
first: 2 second: 3
first: 2 second: 9
fiery && bird ( 1 ) lines match
display_location vector:
first: 2 second: 2
first: 2 second: 3
first: 2 second: 8
first: 2 second: 9
Requested query: fiery && bird
( 3 ) like a fiery bird in flight. A beautiful fiery bird, he tells her,
Приведем трассировку выполнения составного запроса, включающего как И, так и ИЛИ. Показаны векторы позиций каждого операнда, а также результирующий вектор:
==> fiery && ( bird || untamed )
fiery ( 1 ) lines match
display_location vector:
first: 2 second: 3
first: 2 second: 8
bird ( 1 ) lines match
display_location vector:
first: 2 second: 3
first: 2 second: 9
untamed ( 1 ) lines match
display_location vector:
first: 3 second: 2
( bird || untamed ) ( 2 ) lines match
display_location vector:
first: 2 second: 3
first: 2 second: 9
first: 3 second: 2
fiery && ( bird || untamed ) ( 1 ) lines match
display_location vector:
first: 2 second: 2
first: 2 second: 3
first: 2 second: 8
first: 2 second: 9
Requested query: fiery && ( bird || untamed )
( 3 ) like a fiery bird in flight. A beautiful fiery bird, he tells her,
