Наша последняя задача связана с анализом текста, точнее, с проверкой правописания и нахождением мест, где можно поставить перенос для улучшения форматирования.
Ограничения здесь аналогичны тем, о которых уже говорилось при обсуждении форматирования в разделе 2.3. Как и в случае с разбиением на строки, есть много способов реализовать поиск орфографических ошибок и вычисление точек переноса. Поэтому и здесь планировалась поддержка нескольких алгоритмов. Пользователь сможет выбрать тот алгоритм, который его больше устраивает по соотношению потребляемой памяти, скорости и качеству. Добавление новых алгоритмов тоже должно реализовываться просто.
Также мы хотим избежать жесткой привязки этой информации к структуре документа. В данном случае такая цель даже более важна, чем при форматировании, поскольку проверка правописания и расстановка переносов - это лишь два вида анализа текста, которые Lexi мог бы поддерживать. Со временем мы собираемся расширить аналитические возможности Lexi. Мы могли бы добавить поиск, подсчет слов, средства вычислений для суммирования значений в таблице, проверку грамматики и т.д. Но мы не хотим изменять класс Glyph и все его подклассы при каждом добавлении такого рода функциональности.
У этой задачи есть две стороны: доступ к анализируемой информации, которая разбросана по разным глифам в структуре документа и собственно выполнение анализа. Рассмотрим их по отдельности.
Доступ к распределенной информации
Для многих видов анализа необходимо рассматривать текст посимвольно. Но анализируемый текст рассеян по иерархии структур, состоящих из объектов-глифов. Чтобы исследовать текст, представленный в таком виде, нужен механизм доступа, знающий о структурах данных, в которых хранится текст. Для некоторых глифов потомки могут храниться в связанных списках, для других - в массивах, а для третьих и вовсе используются какие-то экзотические структуры. Наш механизм доступа должен справляться со всем этим.
К сожалению, для разных видов анализа методы доступа к информации могут различаться. Обычно текст сканируется от начала к концу. Но иногда требуется сделать прямо противоположное. Например, для реверсивного поиска нужно проходить по тексту в обратном, а не в прямом направлении. А при вычислении алгебраических выражений необходим внутренний порядок обхода.
Итак, наш механизм доступа должен уметь приспосабливаться к разным структурам данных и поддерживать разные способы обхода.
Поэтому только глифу разрешено знать, какую структуру он использует. Отсюда следует, что интерфейс глифов не должен отдавать предпочтение какой-то одной структуре данных. Например, не следует оптимизировать его в пользу массивов, а не связанных списков, как это делалось до сих пор.
Мы можем решить проблему и одновременно поддержать несколько разных способов обхода. Разумно включить возможности множественного доступа и обхода прямо в классы глифов и предоставить способ выбирать между ними, возможно, передавая константу, являющуюся элементом некоторого перечисления. Выполняя обход, классы передают этот параметр друг другу, чтобы гарантировать, что все они обходят структуру в одном и том же порядке. Так же должна передаваться любая информация, собранная во время обхода.
Для поддержки данного подхода мы могли бы добавить в интерфейс класса Glyph следующие абстрактные операции:
void First(Traversal kind)
void Next()
bool IsDone()
Glyph* GetCurrent()
void Insert(Glyph*)
Операции First, Next и IsDone управляют обходом. First производит инициализацию. В качестве параметра передается вид обхода в виде перечисляемой константы типа Traversal, которая может принимать такие значения, как CHILDREN (обходить только прямых потомков глифа), PREORDER (обходить всю структуру в прямом порядке), POSTORDER (в обратном порядке) или INORDER (во внутреннем порядке). Next переходит к следующему глифу в порядке обхода, a IsDone сообщает, закончился ли обход. GetCurrent заменяет операцию Child - осуществляет доступ к текущему в данном обходе глифу. Старая операция Insert переписывается, теперь она вставляет глиф в текущую позицию.
При анализе можно было бы использовать следующий код на C++ для обхода структуры глифов с корнем в g в прямом порядке:
for (g->First(PREORDER); !g->IsDone(); g->Next()) {
Glyph* current = g->GetCurrent();
// выполнить анализ
}
Обратите внимание, что мы исключили целочисленный индекс из интерфейса глифов. Не осталось ничего, что предполагало бы какой-то предпочтительный контейнер. Мы также уберегли клиенты от необходимости самостоятельно реализовывать типичные виды доступа.
Но этот подход еще не идеален. Во-первых, здесь не поддерживаются новые виды обхода, не расширяется множество значений перечисления и не добавляются новые операции. Предположим, что нам нужен вариант прямого обхода, при котором автоматически пропускаются нетекстовые глифы. Тогда пришлось бы изменить перечисление Traversal, включив в него значение TEXTUAL_PREORDER.
Не нежелательно менять уже имеющиеся объявления. Помещение всего механизма обхода в иерархию класса Glyph затрудняет модификацию и расширение без изменения многих других классов. Механизм также трудно использовать повторно для обхода других видов структур. И еще нельзя иметь более одного активного обхода над данной структурой.
Как уже не раз бывало, наилучшее решение - инкапсулировать изменяющуюся сущность в класс. В данном случае это механизмы доступа и обхода. Допустимо ввести класс объектов, называемых итераторами, единственное назначение которых - определить разные наборы таких механизмов. Можно также воспользоваться наследованием для унификации доступа к разным структурам данных и поддержки новых видов обхода. Тогда не придется изменять интерфейсы глифов или трогать реализации существующих глифов.
Обратите внимание, что мы добавили в интерфейс класса Glyph абстрактную операцию CreateIterator для поддержки итераторов.
Интерфейс итератора предоставляет операции First, Next и IsDone для управления обходом. В классе ListIterator реализация операции First указывает на первый элемент списка, a Next перемещает итератор на следующий элемент. Операция IsDone возвращает признак, говорящий о том, перешел ли указатель за последний элемент списка. Операция CurrentItem разыменовывает итератор для возврата глифа, на который он указывает. Класс ArrayIterator делает то же самое с массивами глифов.
Теперь мы можем получить доступ к потомкам в структуре глифа, не зная ее представления:
Glyph* g;
Iterator<Glyph*>* i = g->CreateIterator();
for (i->First(); !i->IsDone(); i->Next()) {
Glyph* child = i->CurrentItem();
// выполнить действие с потомком
}
CreateIterator по умолчанию возвращает экземпляр NullIterator. NullIterator - это вырожденный итератор для глифов, у которых нет потомков, то есть листовых глифов. Операция IsDone для NullIterator всегда возвращает истину.
Подкласс глифа, имеющего потомков, замещает операцию CreateIterator так, что она возвращает экземпляр другого подкласса класса Iterator. Какого именно - зависит от структуры, в которой содержатся потомки. Если подкласс Row класса Glyph размещает потомков в списке, то его операция CreateIterator будет выглядеть примерно так:
Iterator<Glyph*>* Row::CreateIterator () {
return new ListIterator<Glyph*>(_children);
}
Для обхода в прямом и внутреннем порядке итераторы реализуют алгоритм обхода в терминах, определенных для конкретных глифов. В обоих случаях итератору передается корневой глиф той структуры, которую нужно обойти. Итераторы вызывают CreateIterator для каждого глифа в этой структуре и сохраняют возвращенные итераторы в стеке.
Например, класс PreorderIterator получает итератор от корневого глифа, инициализирует его так, чтобы он указывал на свой первый элемент, а затем помещает в стек:
void PreorderIterator::First () {
Iterator<Glyph*>* i = _root->CreateIterator();
if (i) {
i->First();
_iterators.RemoveAll();
_iterators.Push(i);
}
}
CurrentItem должна будет просто вызвать операцию CurrentItem для итератора на вершине стека:
Glyph* PreorderIterator::CurrentItem () const {
return _iterators.Size() > 0 ?
_iterators.Top()->CurrentItem() : 0;
}
Операция Next обращается к итератору с вершины стека с тем, чтобы элемент, на который он указывает, создал свой итератор, спускаясь тем самым по структуре глифов как можно ниже (это ведь прямой порядок, не так ли?). Next устанавливает новый итератор так, чтобы он указывал на первый элемент в порядке обхода, и помещает его в стек. Затем Next проверяет последний встретившийся итератор; если его операция IsDone возвращает true, то обход текущего поддерева (или листа) закончен. В таком случае Next снимает итератор с вершины стека и повторяет всю последовательность действий, пока не найдет следующее не полностью обойденное дерево, если таковое существует. Если же необойденных деревьев больше нет, то мы закончили обход:
void PreorderIterator::Next () {
Iterator<Glyph*>* i =
_iterators.Top()->CurrentItem()->CreateIterator();
i->First();
_iterators.Push(i) ;
while (_iterators.Size() > 0 && _iterators.Top()->IsDone()) {
delete _iterators.Pop();
_iterators.Top()->Next();
}
}
Обратите внимание, что класс Iterator позволяет вводить новые виды обходов, не изменяя классы глифов, - мы просто порождаем новый подкласс и добавляем новый обход так, как проделали это для PreorderIterator. Подклассы класса Glyph пользуются тем же самым интерфейсом, чтобы предоставить клиентам доступ к своим потомкам, не раскрывая внутренней структуры данных, в которой они хранятся. Поскольку итераторы сохраняют собственную копию состояния обхода, то одновременно можно иметь несколько активных итераторов для одной и той же структуры. И, хотя в нашем примере мы занимались обходом структур глифов, ничто не мешает параметризовать класс типа PreorderIterator типом объекта структуры. В C++ мы воспользовались бы для этого шаблонами. Тогда описанный механизм итераторов можно было бы применить для обхода других структур.
Прежде всего следует решить, на какую часть программы возложить ответственность за выполнение анализа. Можно было бы поручить это классам Iterator, тем самым сделав анализ неотъемлемой частью обхода. Но решение стало бы более гибким и пригодным для повторного использования, если бы обход был отделен от действий, которые при этом выполняются. Дело в том, что для одного и того же вида обхода могут выполняться разные виды анализа. Поэтому один и тот же набор итераторов можно было бы использовать для разных аналитических операций. Например, прямой порядок обхода применяется в разных случаях, включая проверку правописания, расстановку переносов, поиск в прямом направлении и подсчет слов.
Итак, анализ и обход следует разделить. Кому еще можно поручить анализ? Мы знаем, что разновидностей анализа достаточно много, и в каждом случае в те или иные моменты обхода будут выполняться различные действия. В зависимости от вида анализа некоторые глифы могут оказаться более важными, чем другие. При проверке правописания и расстановке переносов мы хотели бы рассматривать только символьные глифы и пропускать графические - линии, растровые изображения и т.д. Если мы занимаемся разделением цветов, то желательно было бы принимать во внимание только видимые, но никак не невидимые глифы. Таким образом, разные глифы должны просматриваться разными видами анализа.
Поэтому данный вид анализа должен уметь различать глифы по их типу. Очевидное решение - встроить аналитические возможности в сами классы глифов. Тогда для каждого вида анализа мы можно было добавить одну или несколько абстрактных операций в класс Glyph и реализовать их в подклассах в соответствии с той ролью, которую они играют при анализе.
Однако неприятная особенность такого подхода состоит в том, что придется изменять каждый класс глифов при добавлении нового вида анализа. В некоторых случаях проблему удается сгладить: если в анализе участвует немного классов или если большинство из них выполняют анализ одним и тем же способом, то можно поместить подразумеваемую реализацию абстрактной операции прямо в класс Glyph. Такая операция по умолчанию будет обрабатывать наиболее распространенный случай. Тогда мы смогли бы ограничиться только изменениями класса Glyph и тех его подклассов, которые отклоняются от нормы.
Но, несмотря на то что реализация по умолчанию сокращает объем изменений, принципиальная проблема остается: интерфейс класса Glyph необходимо расширять при добавлении каждого нового вида анализа. Со временем такие операции затемнят смысл этого интерфейса. Будет трудно понять, что основная цель глифа - определить и структурировать объекты, имеющие внешнее представление и форму; в интерфейсе появится много лишних деталей.
Принципиальный вопрос при таком подходе - как объект-анализатор различает виды глифов, не прибегая к проверке или приведениям типов? Мы не хотим, чтобы класс SpellingChecker включал такой псевдокод:
void SpellingChecker::Check (Glyph* glyph) {
Character* c;
Row* r;
Image* i;
if (c = dynamic_cast<Character*>(glyph)) {
// анализировать символ
} else if (r = dynamic_cast<Row*>(glyph)) {
// анализировать потомки r
} else if (i = dynamic_cast<Image*>(glyph)) {
// ничего не делать
}
}
Такой код опирается на специфические возможности безопасных по отношению к типам приведений. Его трудно расширять. Нужно не забыть изменить тело данной функции после любого изменения иерархии класса Glyph. В общем это как раз такой код, необходимость в котором хотелось бы устранить.
Как уйти от данного грубого подхода? Посмотрим, что произойдет, если мы добавим в класс Glyph такую абстрактную операцию:
void CheckMe (SpellingChecker&)
Определим операцию CheckMe в каждом подклассе класса Glyph следующим образом:
void GlyphSubclass :: CheckMe (SpellingChecker& checker) {
checker.CheckGlyphSubclass (this) ;
}
где GlyphSubclass заменяется именем подкласса глифа. Заметим, что при вызове CheckMe конкретный подкласс класса Glyph известен, ведь мы же выполняем одну из его операций. В свою очередь, в интерфейсе класса SpellingChecker есть операция типа CheckGlyphSubclass для каждого подкласса класса Glyph:
Мы могли бы воспользоваться перегрузкой функций, чтобы присвоить этим функциям-членам одинаковые имена, поскольку их можно различить по типам параметров. Здесь мы дали им разные имена, чтобы было видно, что это все-таки разные функции, особенно при их вызове.
Операция проверки в классе SpellingChecker для глифов типа Character могла бы выглядеть так:
Обратите внимание, что мы определили специальную операцию GetCharCode только для класса Character. Объект проверки правописания может работать со специфическими для подклассов операциями, не прибегая к проверке или приведению типов, а это позволяет нам трактовать некоторые объекты специальным образом.
Объект класса CheckCharacter накапливает буквы в буфере _currentWord. Когда встречается не-буква, например символ подчеркивания, этот объект вызывает операцию IsMisspelled для проверки орфографии слова, находящегося в _currentWord.
Функция IsMisspelled реализует алгоритм проверки орфографии, детали которого мы здесь не приводим, поскольку мы сделали его независимым от дизайна Lexi. Мы можем поддержать разные алгоритмы, порождая подклассы класса SpellingChecker. Или применить для этой цели паттерн стратегия (как для форматирования в разделе 2.3).
Если слово написано неправильно, то CheckCharacter добавляет его в список слов с ошибками. Затем буфер _currentWord очищается для приема следующего слова. По завершении обхода можно добраться до списка слов с ошибками с помощью операции GetMisspellings.
Теперь логично обойти всю структуру глифов, вызывая CheckMe для каждого глифа и передавая ей объект проверки правописания в качестве аргумента. Тем самым текущий глиф для SpellingChecker идентифицируется и может продолжать проверку:
SpellingChecker spellingChecker;
Composition* с;
// ...
Glyph* g;
PreorderIterator i(c);
for (i.First (); !i.IsDone(); i.Next()) {
g = i.CurrentItem();
g->CheckMe(spellingChecker) ;
}
На следующей диаграмме показано, как взаимодействуют глифы типа Character и объект SpellingChecker.
Этот подход работает при поиске орфографических ошибок, но как он может помочь в поддержке нескольких видов анализа? Похоже, что придется добавлять операцию вроде CheckMe(SpellingChecker&) в класс Glyph и его подклассы всякий раз, как вводится новый вид анализа. Так оно и есть, если мы настаиваем на независимом классе для каждого вида анализа. Но почему бы не придать всем видам анализа одинаковый интерфейс? Это позволит нам использовать их полиморфно. И тогда мы сможем заменить специфические для конкретного вида анализа операции вроде CheckMe(SpellingChecker&) одной инвариантной операцией, принимающей более общий параметр.
class Visitor {
public:
virtual void VisitCharacter(Character*) { }
virtual void VisitRow(Row*) { }
virtual void Visitlmage(Image*) { }
// ... и так далее
};
Конкретные подклассы Visitor выполняют разные виды анализа. Например, можно было определить подкласс SpellingCheckingVisitor для проверки правописания и подкласс HyphenationVisitor для расстановки переносов. При этом SpellingCheckingVisitor был бы реализован точно так же, как мы реализовали класс SpellingChecker выше, только имена операций отражали бы более общий интерфейс класса Visitor. Так, операция CheckCharacter называлась бы VisitCharacter.
Поскольку имя CheckMe не подходит для посетителей, которые ничего не проверяют, мы использовали бы имя Accept. Аргумент этой операции тоже пришлось бы изменить на Visitor&, чтобы отразить тот факт, что может приниматься любой посетитель. Теперь для добавления нового вида анализа нужно лишь определить новый подкласс класса Visitor, а трогать классы глифов вовсе не обязательно. Мы поддержали все возможные в будущем виды анализа, добавив лишь одну операцию в класс Glyph и его подклассы.
О выполнении проверки правописания говорилось выше. Такой же подход будет применен для аккумулирования текста в подклассе HyphenationVisitor. Но после того как операция VisitCharacter из подкласса HyphenationVisitor закончила распознавание целого слова, она ведет себя по-другому. Вместо проверки орфографии применяется алгоритм расстановки переносов, чтобы определить, в каких местах можно перенести слово на другую строку (если это вообще возможно). Затем для каждой из найденных точек в структуру вставляется разделяющий (discretionary) глиф. Разделяющие глифы являются экземплярами подкласса Glyph - класса Discretionary.
Разделяющий глиф может выглядеть по-разному в зависимости от того, является он последним символом в строке или нет. Если это последний символ, глиф выглядит как дефис, в противном случае не отображается вообще. Разделяющий глиф запрашивает у своего родителя (объекта Row), является ли он последним потомком, и делает это всякий раз, когда от него требуют отобразить себя или вычислить свои размеры. Стратегия форматирования трактует разделяющие глифы точно так же, как пропуски, считая их «кандидатами» на завершающий символ строки. На диаграмме ниже показано, как может выглядеть встроенный разделитель.
Важный вопрос, который надо задать себе перед применением паттерна посетитель, звучит так: «Какие иерархии классов наиболее часто будут изменяться?» Этот паттерн особенно удобен, если необходимо выполнять действия над объектами, принадлежащими классу со стабильной структурой. Добавление нового вида посетителя не требует изменять структуру класса, что особенно важно, когда класс большой. Но при каждом добавлении нового подкласса вы будете вынуждены обновить все интерфейсы посетителя с целью включить операцию Visit... для этого подкласса. В нашем примере это означает, что добавление подкласса Foo класса Glyph потребует изменить класс Visitor и все его подклассы, чтобы добавить операцию Visit Foo. Однако при наших проектных условиях гораздо более вероятно добавление к Lexi нового вида анализа, а не нового вида глифов. Поэтому для наших целей паттерн посетитель вполне подходит.
Инкапсуляция доступа и порядка обхода
Пока что в нашем интерфейсе глифов для доступа к потомкам со стороны клиентов используется целочисленный индекс. Хотя для тех классов глифов, которые содержат потомков в массиве, это, может быть, и разумно, но совершенно неэффективно для глифов, пользующихся связанным списком. Роль абстракции глифов в том, чтобы скрыть структуру данных, в которой содержатся потомки. Тогда мы сможем изменить данную структуру, не затрагивая другие классы.Поэтому только глифу разрешено знать, какую структуру он использует. Отсюда следует, что интерфейс глифов не должен отдавать предпочтение какой-то одной структуре данных. Например, не следует оптимизировать его в пользу массивов, а не связанных списков, как это делалось до сих пор.
Мы можем решить проблему и одновременно поддержать несколько разных способов обхода. Разумно включить возможности множественного доступа и обхода прямо в классы глифов и предоставить способ выбирать между ними, возможно, передавая константу, являющуюся элементом некоторого перечисления. Выполняя обход, классы передают этот параметр друг другу, чтобы гарантировать, что все они обходят структуру в одном и том же порядке. Так же должна передаваться любая информация, собранная во время обхода.
Для поддержки данного подхода мы могли бы добавить в интерфейс класса Glyph следующие абстрактные операции:
void First(Traversal kind)
void Next()
bool IsDone()
Glyph* GetCurrent()
void Insert(Glyph*)
Операции First, Next и IsDone управляют обходом. First производит инициализацию. В качестве параметра передается вид обхода в виде перечисляемой константы типа Traversal, которая может принимать такие значения, как CHILDREN (обходить только прямых потомков глифа), PREORDER (обходить всю структуру в прямом порядке), POSTORDER (в обратном порядке) или INORDER (во внутреннем порядке). Next переходит к следующему глифу в порядке обхода, a IsDone сообщает, закончился ли обход. GetCurrent заменяет операцию Child - осуществляет доступ к текущему в данном обходе глифу. Старая операция Insert переписывается, теперь она вставляет глиф в текущую позицию.
При анализе можно было бы использовать следующий код на C++ для обхода структуры глифов с корнем в g в прямом порядке:
for (g->First(PREORDER); !g->IsDone(); g->Next()) {
Glyph* current = g->GetCurrent();
// выполнить анализ
}
Обратите внимание, что мы исключили целочисленный индекс из интерфейса глифов. Не осталось ничего, что предполагало бы какой-то предпочтительный контейнер. Мы также уберегли клиенты от необходимости самостоятельно реализовывать типичные виды доступа.
Но этот подход еще не идеален. Во-первых, здесь не поддерживаются новые виды обхода, не расширяется множество значений перечисления и не добавляются новые операции. Предположим, что нам нужен вариант прямого обхода, при котором автоматически пропускаются нетекстовые глифы. Тогда пришлось бы изменить перечисление Traversal, включив в него значение TEXTUAL_PREORDER.
Не нежелательно менять уже имеющиеся объявления. Помещение всего механизма обхода в иерархию класса Glyph затрудняет модификацию и расширение без изменения многих других классов. Механизм также трудно использовать повторно для обхода других видов структур. И еще нельзя иметь более одного активного обхода над данной структурой.
Как уже не раз бывало, наилучшее решение - инкапсулировать изменяющуюся сущность в класс. В данном случае это механизмы доступа и обхода. Допустимо ввести класс объектов, называемых итераторами, единственное назначение которых - определить разные наборы таких механизмов. Можно также воспользоваться наследованием для унификации доступа к разным структурам данных и поддержки новых видов обхода. Тогда не придется изменять интерфейсы глифов или трогать реализации существующих глифов.
Класс Iterator и его подклассы
Мы применим абстрактный класс Iterator для определения общего интерфейса доступа и обхода. Конкретные подклассы вроде ArrayIterator и ListIterator реализуют данный интерфейс для предоставления доступа к массивам и спискам, а такие подклассы, как PreorderIterator, PostorderIterator и им подобные, реализуют разные виды обходов структур. Каждый подкласс класса Iterator содержит ссылку на структуру, которую он обходит. Экземпляры подкласса инициализируются этой ссылкой при создании. На рис. 2.13 показан класс Iterator и несколько его подклассов.Обратите внимание, что мы добавили в интерфейс класса Glyph абстрактную операцию CreateIterator для поддержки итераторов.
Интерфейс итератора предоставляет операции First, Next и IsDone для управления обходом. В классе ListIterator реализация операции First указывает на первый элемент списка, a Next перемещает итератор на следующий элемент. Операция IsDone возвращает признак, говорящий о том, перешел ли указатель за последний элемент списка. Операция CurrentItem разыменовывает итератор для возврата глифа, на который он указывает. Класс ArrayIterator делает то же самое с массивами глифов.
Теперь мы можем получить доступ к потомкам в структуре глифа, не зная ее представления:
Glyph* g;
Iterator<Glyph*>* i = g->CreateIterator();
for (i->First(); !i->IsDone(); i->Next()) {
Glyph* child = i->CurrentItem();
// выполнить действие с потомком
}
CreateIterator по умолчанию возвращает экземпляр NullIterator. NullIterator - это вырожденный итератор для глифов, у которых нет потомков, то есть листовых глифов. Операция IsDone для NullIterator всегда возвращает истину.
Подкласс глифа, имеющего потомков, замещает операцию CreateIterator так, что она возвращает экземпляр другого подкласса класса Iterator. Какого именно - зависит от структуры, в которой содержатся потомки. Если подкласс Row класса Glyph размещает потомков в списке, то его операция CreateIterator будет выглядеть примерно так:
Iterator<Glyph*>* Row::CreateIterator () {
return new ListIterator<Glyph*>(_children);
}
Для обхода в прямом и внутреннем порядке итераторы реализуют алгоритм обхода в терминах, определенных для конкретных глифов. В обоих случаях итератору передается корневой глиф той структуры, которую нужно обойти. Итераторы вызывают CreateIterator для каждого глифа в этой структуре и сохраняют возвращенные итераторы в стеке.
Например, класс PreorderIterator получает итератор от корневого глифа, инициализирует его так, чтобы он указывал на свой первый элемент, а затем помещает в стек:
void PreorderIterator::First () {
Iterator<Glyph*>* i = _root->CreateIterator();
if (i) {
i->First();
_iterators.RemoveAll();
_iterators.Push(i);
}
}
CurrentItem должна будет просто вызвать операцию CurrentItem для итератора на вершине стека:
Glyph* PreorderIterator::CurrentItem () const {
return _iterators.Size() > 0 ?
_iterators.Top()->CurrentItem() : 0;
}
Операция Next обращается к итератору с вершины стека с тем, чтобы элемент, на который он указывает, создал свой итератор, спускаясь тем самым по структуре глифов как можно ниже (это ведь прямой порядок, не так ли?). Next устанавливает новый итератор так, чтобы он указывал на первый элемент в порядке обхода, и помещает его в стек. Затем Next проверяет последний встретившийся итератор; если его операция IsDone возвращает true, то обход текущего поддерева (или листа) закончен. В таком случае Next снимает итератор с вершины стека и повторяет всю последовательность действий, пока не найдет следующее не полностью обойденное дерево, если таковое существует. Если же необойденных деревьев больше нет, то мы закончили обход:
void PreorderIterator::Next () {
Iterator<Glyph*>* i =
_iterators.Top()->CurrentItem()->CreateIterator();
i->First();
_iterators.Push(i) ;
while (_iterators.Size() > 0 && _iterators.Top()->IsDone()) {
delete _iterators.Pop();
_iterators.Top()->Next();
}
}
Обратите внимание, что класс Iterator позволяет вводить новые виды обходов, не изменяя классы глифов, - мы просто порождаем новый подкласс и добавляем новый обход так, как проделали это для PreorderIterator. Подклассы класса Glyph пользуются тем же самым интерфейсом, чтобы предоставить клиентам доступ к своим потомкам, не раскрывая внутренней структуры данных, в которой они хранятся. Поскольку итераторы сохраняют собственную копию состояния обхода, то одновременно можно иметь несколько активных итераторов для одной и той же структуры. И, хотя в нашем примере мы занимались обходом структур глифов, ничто не мешает параметризовать класс типа PreorderIterator типом объекта структуры. В C++ мы воспользовались бы для этого шаблонами. Тогда описанный механизм итераторов можно было бы применить для обхода других структур.
Паттерн итератор
Паттерн итератор абстрагирует описанную технику поддержки обхода структур, состоящих из объектов, и доступа к их элементам. Он применим не только к составным структурам, но и к группам, абстрагирует алгоритм обхода и экранирует клиентов от деталей внутренней структуры объектов, которые они обходят. Паттерн итератор - это еще один пример того, как инкапсуляция изменяющейся сущности помогает достичь гибкости и повторной используемости. Но все равно проблема итерации оказывается глубокой, поэтому паттерн итератор гораздо сложней, чем было рассмотрено выше.Обход и действия, выполняемые при обходе
Итак, теперь, когда у нас есть способ обойти структуру глифов, нужно заняться проверкой правописания и расстановкой переносов. Для обоих видов анализа необходимо аккумулировать собранную во время обхода информацию.Прежде всего следует решить, на какую часть программы возложить ответственность за выполнение анализа. Можно было бы поручить это классам Iterator, тем самым сделав анализ неотъемлемой частью обхода. Но решение стало бы более гибким и пригодным для повторного использования, если бы обход был отделен от действий, которые при этом выполняются. Дело в том, что для одного и того же вида обхода могут выполняться разные виды анализа. Поэтому один и тот же набор итераторов можно было бы использовать для разных аналитических операций. Например, прямой порядок обхода применяется в разных случаях, включая проверку правописания, расстановку переносов, поиск в прямом направлении и подсчет слов.
Итак, анализ и обход следует разделить. Кому еще можно поручить анализ? Мы знаем, что разновидностей анализа достаточно много, и в каждом случае в те или иные моменты обхода будут выполняться различные действия. В зависимости от вида анализа некоторые глифы могут оказаться более важными, чем другие. При проверке правописания и расстановке переносов мы хотели бы рассматривать только символьные глифы и пропускать графические - линии, растровые изображения и т.д. Если мы занимаемся разделением цветов, то желательно было бы принимать во внимание только видимые, но никак не невидимые глифы. Таким образом, разные глифы должны просматриваться разными видами анализа.
Поэтому данный вид анализа должен уметь различать глифы по их типу. Очевидное решение - встроить аналитические возможности в сами классы глифов. Тогда для каждого вида анализа мы можно было добавить одну или несколько абстрактных операций в класс Glyph и реализовать их в подклассах в соответствии с той ролью, которую они играют при анализе.
Однако неприятная особенность такого подхода состоит в том, что придется изменять каждый класс глифов при добавлении нового вида анализа. В некоторых случаях проблему удается сгладить: если в анализе участвует немного классов или если большинство из них выполняют анализ одним и тем же способом, то можно поместить подразумеваемую реализацию абстрактной операции прямо в класс Glyph. Такая операция по умолчанию будет обрабатывать наиболее распространенный случай. Тогда мы смогли бы ограничиться только изменениями класса Glyph и тех его подклассов, которые отклоняются от нормы.
Но, несмотря на то что реализация по умолчанию сокращает объем изменений, принципиальная проблема остается: интерфейс класса Glyph необходимо расширять при добавлении каждого нового вида анализа. Со временем такие операции затемнят смысл этого интерфейса. Будет трудно понять, что основная цель глифа - определить и структурировать объекты, имеющие внешнее представление и форму; в интерфейсе появится много лишних деталей.
Инкапсуляция анализа
Судя по всему, стоит инкапсулировать анализ в отдельный объект, как мы уже много раз делали прежде. Можно было бы поместить механизм конкретного вида анализа в его собственный класс, а экземпляр этого класса использовать совместно с подходящим итератором. Тогда итератор «переносил» бы этот экземпляр от одного глифа к другому, а объект выполнял бы свой анализ для каждого элемента. По мере продвижения обхода анализатор накапливал бы определенную информацию (в данном случае - символы):Принципиальный вопрос при таком подходе - как объект-анализатор различает виды глифов, не прибегая к проверке или приведениям типов? Мы не хотим, чтобы класс SpellingChecker включал такой псевдокод:
void SpellingChecker::Check (Glyph* glyph) {
Character* c;
Row* r;
Image* i;
if (c = dynamic_cast<Character*>(glyph)) {
// анализировать символ
} else if (r = dynamic_cast<Row*>(glyph)) {
// анализировать потомки r
} else if (i = dynamic_cast<Image*>(glyph)) {
// ничего не делать
}
}
Такой код опирается на специфические возможности безопасных по отношению к типам приведений. Его трудно расширять. Нужно не забыть изменить тело данной функции после любого изменения иерархии класса Glyph. В общем это как раз такой код, необходимость в котором хотелось бы устранить.
Как уйти от данного грубого подхода? Посмотрим, что произойдет, если мы добавим в класс Glyph такую абстрактную операцию:
void CheckMe (SpellingChecker&)
Определим операцию CheckMe в каждом подклассе класса Glyph следующим образом:
void GlyphSubclass :: CheckMe (SpellingChecker& checker) {
checker.CheckGlyphSubclass (this) ;
}
где GlyphSubclass заменяется именем подкласса глифа. Заметим, что при вызове CheckMe конкретный подкласс класса Glyph известен, ведь мы же выполняем одну из его операций. В свою очередь, в интерфейсе класса SpellingChecker есть операция типа CheckGlyphSubclass для каждого подкласса класса Glyph:
Мы могли бы воспользоваться перегрузкой функций, чтобы присвоить этим функциям-членам одинаковые имена, поскольку их можно различить по типам параметров. Здесь мы дали им разные имена, чтобы было видно, что это все-таки разные функции, особенно при их вызове.
Операция проверки в классе SpellingChecker для глифов типа Character могла бы выглядеть так:
Обратите внимание, что мы определили специальную операцию GetCharCode только для класса Character. Объект проверки правописания может работать со специфическими для подклассов операциями, не прибегая к проверке или приведению типов, а это позволяет нам трактовать некоторые объекты специальным образом.
Объект класса CheckCharacter накапливает буквы в буфере _currentWord. Когда встречается не-буква, например символ подчеркивания, этот объект вызывает операцию IsMisspelled для проверки орфографии слова, находящегося в _currentWord.
Функция IsMisspelled реализует алгоритм проверки орфографии, детали которого мы здесь не приводим, поскольку мы сделали его независимым от дизайна Lexi. Мы можем поддержать разные алгоритмы, порождая подклассы класса SpellingChecker. Или применить для этой цели паттерн стратегия (как для форматирования в разделе 2.3).
Если слово написано неправильно, то CheckCharacter добавляет его в список слов с ошибками. Затем буфер _currentWord очищается для приема следующего слова. По завершении обхода можно добраться до списка слов с ошибками с помощью операции GetMisspellings.
Теперь логично обойти всю структуру глифов, вызывая CheckMe для каждого глифа и передавая ей объект проверки правописания в качестве аргумента. Тем самым текущий глиф для SpellingChecker идентифицируется и может продолжать проверку:
SpellingChecker spellingChecker;
Composition* с;
// ...
Glyph* g;
PreorderIterator i(c);
for (i.First (); !i.IsDone(); i.Next()) {
g = i.CurrentItem();
g->CheckMe(spellingChecker) ;
}
На следующей диаграмме показано, как взаимодействуют глифы типа Character и объект SpellingChecker.
Этот подход работает при поиске орфографических ошибок, но как он может помочь в поддержке нескольких видов анализа? Похоже, что придется добавлять операцию вроде CheckMe(SpellingChecker&) в класс Glyph и его подклассы всякий раз, как вводится новый вид анализа. Так оно и есть, если мы настаиваем на независимом классе для каждого вида анализа. Но почему бы не придать всем видам анализа одинаковый интерфейс? Это позволит нам использовать их полиморфно. И тогда мы сможем заменить специфические для конкретного вида анализа операции вроде CheckMe(SpellingChecker&) одной инвариантной операцией, принимающей более общий параметр.
Класс Visitor и его подклассы
Мы будем использовать термин «посетитель» для обозначения класса объектов, «посещающих» другие объекты во время обхода, дабы сделать то, что необходимо в данном контексте. «Посетить» - это лишь немногим более общее слово, чем «проанализировать». Оно просто предвосхищает ту терминологию, которой мы будем пользоваться при обсуждении следующего паттерна. Тогда мы можем определить класс Visitor, описывающий абстрактный интерфейс для посещения глифов в структуре:class Visitor {
public:
virtual void VisitCharacter(Character*) { }
virtual void VisitRow(Row*) { }
virtual void Visitlmage(Image*) { }
// ... и так далее
};
Конкретные подклассы Visitor выполняют разные виды анализа. Например, можно было определить подкласс SpellingCheckingVisitor для проверки правописания и подкласс HyphenationVisitor для расстановки переносов. При этом SpellingCheckingVisitor был бы реализован точно так же, как мы реализовали класс SpellingChecker выше, только имена операций отражали бы более общий интерфейс класса Visitor. Так, операция CheckCharacter называлась бы VisitCharacter.
Поскольку имя CheckMe не подходит для посетителей, которые ничего не проверяют, мы использовали бы имя Accept. Аргумент этой операции тоже пришлось бы изменить на Visitor&, чтобы отразить тот факт, что может приниматься любой посетитель. Теперь для добавления нового вида анализа нужно лишь определить новый подкласс класса Visitor, а трогать классы глифов вовсе не обязательно. Мы поддержали все возможные в будущем виды анализа, добавив лишь одну операцию в класс Glyph и его подклассы.
О выполнении проверки правописания говорилось выше. Такой же подход будет применен для аккумулирования текста в подклассе HyphenationVisitor. Но после того как операция VisitCharacter из подкласса HyphenationVisitor закончила распознавание целого слова, она ведет себя по-другому. Вместо проверки орфографии применяется алгоритм расстановки переносов, чтобы определить, в каких местах можно перенести слово на другую строку (если это вообще возможно). Затем для каждой из найденных точек в структуру вставляется разделяющий (discretionary) глиф. Разделяющие глифы являются экземплярами подкласса Glyph - класса Discretionary.
Разделяющий глиф может выглядеть по-разному в зависимости от того, является он последним символом в строке или нет. Если это последний символ, глиф выглядит как дефис, в противном случае не отображается вообще. Разделяющий глиф запрашивает у своего родителя (объекта Row), является ли он последним потомком, и делает это всякий раз, когда от него требуют отобразить себя или вычислить свои размеры. Стратегия форматирования трактует разделяющие глифы точно так же, как пропуски, считая их «кандидатами» на завершающий символ строки. На диаграмме ниже показано, как может выглядеть встроенный разделитель.
Паттерн посетитель
Вышеописанная процедура - пример применения паттерна посетитель. Его главными участниками являются класс Visitor и его подклассы. Паттерн посетитель абстрагирует метод, позволяющий иметь заранее неопределенное число видов анализа структур глифов без изменения самих классов глифов. Еще одна полезная особенность посетителей состоит в том, что их можно применять не только к таким агрегатам, как наши структуры глифов, но и к любым структурам, состоящим из объектов. Сюда входят множества, списки и даже направленные ациклические графы. Более того, классы, которые обходит посетитель, необязательно должны быть связаны друг с другом через общий родительский класс. А это значит, что посетители могут пересекать границы иерархий классов.Важный вопрос, который надо задать себе перед применением паттерна посетитель, звучит так: «Какие иерархии классов наиболее часто будут изменяться?» Этот паттерн особенно удобен, если необходимо выполнять действия над объектами, принадлежащими классу со стабильной структурой. Добавление нового вида посетителя не требует изменять структуру класса, что особенно важно, когда класс большой. Но при каждом добавлении нового подкласса вы будете вынуждены обновить все интерфейсы посетителя с целью включить операцию Visit... для этого подкласса. В нашем примере это означает, что добавление подкласса Foo класса Glyph потребует изменить класс Visitor и все его подклассы, чтобы добавить операцию Visit Foo. Однако при наших проектных условиях гораздо более вероятно добавление к Lexi нового вида анализа, а не нового вида глифов. Поэтому для наших целей паттерн посетитель вполне подходит.
