17.7. Управляющий класс UserQuery

17.7. Управляющий класс UserQuery

Если имеется запрос такого типа:

fiery && ( bird || potato )

то в нашу задачу входит построение эквивалентной иерархии классов:

AndQuery

NameQuery( "fiery" )

OrQuery

NameQuery( "bird" )

NameQuery( "potato" )

Как лучше всего это сделать? Процедура вычисления ответа на запрос напоминает функционирование конечного автомата. Мы начинаем с пустого состояния и при обработке каждого элемента запроса переходим в новое состояние, пока весь запрос не будет разобран. В основе нашей реализации лежит одна инструкция switch внутри операции, которую мы назвали eval_query(). Слова запроса считываются одно за другим из вектора строк и сравниваются с каждым из возможных значений:

vectorstring::iterator

it = _query-begin(),

end_it = _query-end();

for ( ; it != end_it; ++it )

switch( evalQueryString( *it ))

{

case WORD:

evalWord( *it );

break;

case AND:

evalAnd();

break;

case OR:

evalOr();

break;

case NOT:

evalNot();

break;

case LPAREN:

++_paren;

++_lparenOn;

break;

case RPAREN:

--_paren;

++_rparenOn;

evalRParen();

break;

}

Пять операций eval: evalWord(), evalAnd(), evalOr(), evalNot и evalRParen() - как раз и строят иерархию классов Query. Прежде чем обратиться к деталям их реализации, рассмотрим общую организацию программы.

Нам нужно определить каждую операцию в виде отдельной функции, как это было сделано в главе 6 при построении процедур обработки запроса. Пользовательский запрос и производные от Query классы представляют независимые данные, которыми оперируют эти функции. От такой модели программирования (она называется процедурной) мы предпочли отказаться.

В разделе 6.14 мы ввели класс TextQuery, где инкапсулировали операции и данные, изучавшиеся в главе 6. Здесь нам потребуется класс UserQuery, решающий аналогичные задачи.

Одним из членов этого класса должен быть вектор строк, содержащий сам запрос пользователя. Другой член - это указатель типа Query* на иерархическое представление запроса, построенное в eval_query(). Еще три члена служат для обработки скобок:

_paren помогает изменить подразумеваемый порядок вычисления операторов (чуть позже мы продемонстрируем это на примере);

_lparenOn и _rparenOn содержат счетчики левых и правых скобок, ассоциированные с текущим узлом дерева разбора запроса (мы показывали, как они используются, при обсуждении виртуальной функции print() в разделе 17.5.1).

Помимо этих пяти членов, нам понадобятся еще два. Рассмотрим следующий запрос:

fiery || untamed

Наша цель - представить его в виде следующего объекта OrQuery:

OrQuery

NameQuery( "fiery" )

NameQuery( "untamed" )

Однако порядок обработки такого запроса вызывает некоторые проблемы. Когда мы определяем объект NameQuery, объект OrQuery , к которому его надо добавить, еще не определен. Поэтому необходимо место, где можно временно сохранить объект NameQuery.

Чтобы сохранить что-либо для последующего использования, традиционно применяется стек. Поместим туда наш объект NameQuery. А когда позже встретим оператор ИЛИ (объект OrQuery), то достанем NameQuery из стека и присоединим его к OrQuery в качестве левого операнда.

Объект OrQuery неполон: в нем не хватает правого операнда. До тех пор пока этот операнд не будет построен, работу с данным объектом придется прекратить.

Его можно поместить в тот же самый стек, что и NameQuery. Однако OrQuery представляет другое состояние обработки запроса: это неполный оператор. Поэтому мы определим два стека: _query_stack для хранения объектов, представляющих сконструированные операнды составного запроса (туда мы помещаем объект NameQuery), а второй для хранения неполных операторов с отсутствующим правым операндом. Второй стек можно трактовать как место для хранения текущей операции, подлежащей завершению, поэтому назовем его _current_op. Сюда мы и поместим объект OrQuery. После того как второй объект NameQuery будет определен, мы достанем объект OrQuery из стека _current_op и добавим к нему NameQuery в качестве правого операнда. Теперь объект OrQuery завершен и мы можем поместить его в стек _query_stack.

Если обработка запроса завершилась нормально, то стек _current_op пуст, а в стеке _query_stack содержится единственный объект, который и представляет весь пользовательский запрос. В нашем случае это объект класса OrQuery.

Рассмотрим несколько примеров. Первый из них - простой запрос типа NotQuery:

! daddy

Ниже показана трассировка его обработки. Финальным объектом в стеке _query_stack является объект класса NotQuery:

evalNot() : incomplete!

push on _current_op ( size == 1 )

evalWord() : daddy

pop _current_op : NotQuery

add operand: WordQuery : NotQuery complete!

push NotQuery on _query_stack

Текст, расположенный с отступом под функциями eval, показывает, как выполняется операция.

Во втором примере - составном запросе типа OrQuery - встречаются оба случая. Здесь же иллюстрируется помещение полного оператора в стек _query_stack:

== fiery || untamed || shyly

evalWord() : fiery

push word on _query_stack

evalOr() : incomplete!

pop _query_stack : fiery

add operand : WordQuery : OrQuery incomplete!

push OrQuery on _current_op ( size == 1 )

evalWord() : untamed

pop _current_op : OrQuery

add operand : WordQuery : OrQuery complete!

push OrQuery on _query_stack

evalOr() : incomplete!

pop _query_stack : OrQuery

add operand : OrQuery : OrQuery incomplete!

push OrQuery on _current_op ( size == 1 )

evalWord() : shyly

pop _current_op : OrQuery

add operand : WordQuery : OrQuery complete!

push OrQuery on _query_stack

В последнем примере рассматривается составной запрос и применение скобок для изменения порядка вычислений:

== fiery && ( bird || untamed )

evalWord() : fiery

push word on _query_stack

evalAnd() : incomplete!

pop _query_stack : fiery

add operand : WordQuery : AndQuery incomplete!

push AndQuery on _current_op ( size == 1 )

evalWord() : bird

_paren is set to 1

push word on _query_stack

evalOr() : incomplete!

pop _query_stack : bird

add operand : WordQuery : OrQuery incomplete!

push OrQuery on _current_op ( size == 2 )

evalWord() : untamed

pop _current_op : OrQuery

add operand : WordQuery : OrQuery complete!

push OrQuery on _query_stack

evalRParen() :

_paren: 0 _current_op.size(): 1

pop _query_stack : OrQuery

pop _current_op : AndQuery

add operand : OrQuery : AndQuery complete!

push AndQuery on _query_stack

Реализация системы текстового поиска состоит из трех компонентов:

класс TextQuery, где производится обработка текста (подробно он рассматривался в разделе 16.4). Для него нет производных классов;

объектно-ориентированная иерархия Query для представления и обработки различных типов запросов;

класс UserQuery, с помощью которого представлен конечный автомат для построения иерархии Query.

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

классы AndQuery, OrQuery и NotQuery требуют, чтобы каждый операнд присутствовал в момент определения объекта. Однако принятая нами схема обработки подразумевает наличие неполных объектов;

наша схема предполагает отложенное добавление операнда к объектам AndQuery, OrQuery и NotQuery. Более того, такая операция должна быть виртуальной. Операнд приходится добавлять через указатель типа Query*, находящийся в стеке _current_op. Однако способ добавления операнда зависит от типа: для унарных (NotQuery) и бинарных (AndQuery и OrQuery) операций он различен. Наша иерархия классов Query подобные операции не поддерживает.

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

В таком случае мы должны либо сами модифицировать иерархию классов Query, либо договориться, чтобы это сделали за нас. В данной ситуации мы, как авторы всей системы, сами изменим код, модифицировав конструкторы подтипов и включив виртуальную функцию-член add_op() для добавления операндов после определения оператора (мы покажем, как она применяется, чуть ниже, при рассмотрении функций evalRParen() и evalWord()).

17.7.1. Определение класса UserQuery

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

// определить объект, не имея запроса пользователя

UserQuery user_query;

string text;

vectorstring query_text;

// обработать запросы пользователя

do {

while( cin text )

query_text.push_back( text );

// передать запрос объекту UserQuery

user_query.query( &query_text );

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

// корень иерархии Query*

Query *query = user_query.eval_query();

}

while ( /* пользователь продолжает формулировать запросы */ );

Вот определение нашего класса UserQuery:

#ifndef USER_QUERY_H

#define USER_QUERY_H

#include string

#include vector

#include map

#include stack

typedef pairshort,short location;

typedef vectorlocation,allocator loc;

#include quot;Query.h"t;

class UserQuery {

public:

UserQuery( vector string,allocator *pquery = 0 )

: _query( pquery ), _eval( 0 ), _paren( 0 ) {}

Query *eval_query(); // строит иерархию

void query( vector string,allocator *pq );

void displayQuery();

static void word_map( mapstring,loc*,lessstring,allocator *pwm ) {

if ( !_word_map ) _word_map = pwm;

}

private:

enum QueryType { WORD = 1, AND, OR, NOT, RPAREN, LPAREN };

QueryType evalQueryString( const string &query );

void evalWord( const string &query );

void evalAnd();

void evalOr();

void evalNot();

void evalRParen();

bool integrity_check();

int _paren;

Query *_eval;

vectorstring *_query;

stackQuery*, vectorQuery* _query_stack;

stackQuery*, vectorQuery* _current_op;

static short _lparenOn, _rparenOn;

static mapstring,loc*,lessstring,allocator *_word_map;

};

#endif

Обратите внимание, что два объявленных нами стека содержат указатели на объекты типа Query, а не сами объекты. Хотя правильное поведение обеспечивается обеими реализациями, хранение объектов значительно менее эффективно, поскольку каждый объект (и его операнды) должен быть почленно скопирован в стек (напомним, что операнды копируются виртуальной функцией clone()) только для того, чтобы вскоре быть уничтоженным. Если мы не собираемся модифицировать объекты, помещаемые в контейнер, то хранение указателей на них намного эффективнее.

Ниже показаны реализации различных встроенных операций eval. Операции evalAnd() и evalOr() выполняют следующие шаги. Сначала объект извлекается из стека _query_stack (напомним, что для класса stack, определенного в стандартной библиотеке, это требует двух операций: top() для получения элемента и pop() для удаления его из стека). Затем из хипа выделяется память для объекта класса AndQuery или OrQuery, и указатель на него передается объекту, извлеченному из стека. Каждая операция передает объекту AndQuery или OrQuery счетчики левых или правых скобок, необходимые ему для вывода своего содержимого. И наконец неполный оператор помещается в стек _current_op:

inline void

UserQuery::

evalAnd()

{

Query *pop = _query_stack.top(); _query_stack.pop();

AndQuery *pq = new AndQuery( pop );

if ( _lparenOn )

{ pq-lparen( _lparenOn ); _lparenOn = 0; }

if ( _rparenOn )

{ pq-rparen( _rparenOn ); _rparenOn = 0; }

_current_op.push( pq );

}

inline void

UserQuery::

evalOr()

{

Query *pop = _query_stack.top(); _query_stack.pop();

OrQuery *pq = new OrQuery( pop );

if ( _lparenOn )

{ pq-lparen( _lparenOn ); _lparenOn = 0; }

if ( _rparenOn )

{ pq-rparen( _rparenOn ); _rparenOn = 0; }

_current_op.push( pq );

}

Операция evalNot() работает следующим образом. В хипе создается новый объект класса NotQuery, которому передаются счетчики левых и правых скобок для правильного отображения содержимого. Затем неполный оператор помещается в стек _current_op:

inline void

UserQuery::

evalNot()

{

NotQuery *pq = new NotQuery;

if ( _lparenOn )

{ pq-lparen( _lparenOn ); _lparenOn = 0; }

if ( _rparenOn )

{ pq-rparen( _rparenOn ); _rparenOn = 0; }

_current_op.push( pq );

}

При обнаружении закрывающей скобки вызывается операция evalRParen(). Если число активных левых скобок больше числа элементов в стеке _current_op, то ничего не происходит. В противном случае выполняются следующие действия. Из стека _query_stack извлекается текущий еще не присоединенный к оператору операнд, а из стека _current_op - текущий неполный оператор. Вызывается виртуальная функция add_op() класса Query, которая их объединяет. И наконец полный оператор помещается в стек _query_stack:

inline void

UserQuery::

evalRParen()

{

if ( _paren _current_op.size() )

{

Query *poperand = _query_stack.top();

_query_stack.pop();

Query *pop = _current_op.top();

_current_op.pop();

pop-add_op( poperand );

_query_stack.push( pop );

}

}

Операция evalWord() выполняет следующие действия. Она ищет указанное слово в отображении _word_map взятых из файла слов на векторы позиций. Если слово найдено, берется его вектор позиций и в хипе посредством конструктора с двумя параметрами создается новый объект NameQuery. В противном случае объект порождается с помощью конструктора с одним параметром. Если число элементов в стеке _current_op меньше либо равно числу встреченных ранее скобок, то нет неполного оператора, ожидающего операнда типа NameQuery, поэтому новый объект помещается в стек _query_stack. Иначе из стека _current_op извлекается неполный оператор, к которому с помощью виртуальной функции add_op() присоединяется операнд NameQuery, после чего ставший полным оператор помещается в стек _query_stack:

inline void

UserQuery::

evalWord( const string &query )

{

NameQuery *pq;

loc *ploc;

if ( ! _word_map-count( query ))

pq = new NameQuery( query );

else {

ploc = ( *_word_map )[ query ];

pq = new NameQuery( query, *ploc );

}

if ( _current_op.size() = _paren )

_query_stack.push( pq );

else {

Query *pop = _current_op.top();

_current_op.pop();

pop-add_op( pq );

_query_stack.push( pop );

}

}

Упражнение 17.21

Напишите деструктор, копирующий конструктор и копирующий оператор присваивания для класса UserQuery.

Упражнение 17.22

Напишите функции print() для класса UserQuery. Обоснуйте свой выбор того, что она выводит.