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; а когда mi предъявляем строки пользователю, mi нумеруем их с единицы.) Поэтому при вычислении ответа создается вектор, содержащий начальные позиции слов в строках 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 loci, location loc2 )

return (( locl.first < loc2.first )

( locl.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 ss

riter != riter end )

пока номер строки в левом векторе больше, чем в правом while ( (*liter).first > (*riter).first ) {

if ( riter == riter end ) return;

пока номер строки в левом векторе меньше, чем в правом while ( (*liter).first < (*riter).first )

если соответствие найдено для последнего слова

в одной строке и первого слова в следящей

max col идентифицирует последнее слово в строке

if ( ((*liter).first == (*riter).first-1 ) ss ((*riter).second == 0 ) ss

((*liter).second == (* max col)[ (*liter).first ] ))

loc.push back( *liter ); loc.push back( *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;

if ( liter == liter end riter == riter end ) return;