<< Пред.           стр. 87 (из 121)           След. >>

Список литературы по разделу

  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;
 vector 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
 #include
 #include
 #include
 
 typedef pair location;
 typedef vector loc;
 
 #include "Query.h"
 
 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( map,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;
  vector *_query;
 
  stack > _query_stack;
  stack > _current_op;
  static short _lparenOn, _rparenOn;
  static map,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. Обоснуйте свой выбор того, что она выводит.
 17.8. Соберем все вместе
 Функция main() для нашего приложения текстового поиска выглядит следующим образом:
 #include "TextQuery.h"
 
 int main()
 {
  TextQuery tq;
 
  tq.build_up_text();
  tq.query_text();
 }
 Функция-член build_text_map() – это не что иное, как переименованная функция doit() из раздела 6.14:
 inline void
 TextQuery::
 build_text_map()
 {
  retrieve_text();
  separate_words();
  filter_text();
  suffix_text();
  strip_caps();
  build_word_map();
 }
 Функция-член query_text() заменяет одноименную функцию из раздела 6.14. В первоначальной реализации в ее обязанности входили прием запроса от пользователя и вывод ответа. Мы решили сохранить за query_text() эти задачи, но реализовать ее по-другому:
 void
 TextQuery::query_text()
 {
  /* локальные объекты:
  *
  * text: содержит все слова запроса
  * query_text: вектор для хранения пользовательского запроса
  * caps: фильтр для поддержки преобразования
  * прописных букв в строчные
  *
  * user_query: объект UserQuery, в котором инкапсулировано
  * собственно вычисление ответа на запрос
  */
  string text;
  string caps( "ABCDEFGHIJKLMNOPQRSTUVWXYZ" );
  vector query_text;
  UserQuery user_query;
 
  // инициализировать статические члены UserQuery
  NotQuery::all_locs( text_locations->second );
  AndQuery::max_col( &line_cnt );
  UserQuery::word_map( word_map );
 
  do {
  // удалить предыдущий запрос, если он был
  query_text.clear();
 
  cout << "Введите запрос. Пожалуйста, разделяйте все его "
  << "элементы пробелами.\n"
  << "Запрос (или весь сеанс) завершается точкой ( . ).\n\n"
  << "==> ";
 
  /*
  * прочитать запрос из стандартного ввода,
  * преобразовать все заглавные буквы, после чего
  * упаковать его в query_text ...
  *
  * примечание: здесь производятся все действия по
  * обработке запроса, связанные собственно с текстом ...
  */
  while( cin >> text )
  {
  if ( text == "." )
  break;
 
  string::size_type pos = 0;
  while (( pos = text.find_first_of( caps, pos ))
  != string::npos )
  text[pos] = tolower( text[pos] );
 
  query_text.push_back( text );
  }
 
  // теперь у нас есть внутреннее представление запроса
  // обработаем его ...
  if ( ! query_text.empty() )
  {
  // передать запрос объекту UserQuery
  user_query.query( &query_text );
  // вычислить ответ на запрос
  // вернуть иерархию Query*

<< Пред.           стр. 87 (из 121)           След. >>

Список литературы по разделу