CodeLAB
на главную карта сайта обратная связь

Популярные задачи:

#Древовидные структуры. (58478 hits)
#Рисование окружности (по Брезенхэму). (34828 hits)
#Полезные утилиты, небольшие api и библиотеки и проч.. (70842 hits)
#"The Java Programming Language" Ken Arnold, James Gosling, David Holmes листинги, код, примеры из книги, исходники. (61988 hits)
#Подключение. (28304 hits)
#Сравнение алгоритмов быстрой сортировки. (75083 hits)
#Вращение 3D объекта. (36941 hits)
#Обновление нескольких записей таблицы. (33401 hits)
#Рисование линии. (39709 hits)
#Циклический сдвиг массива или строки - 3 уникальных алгоритма. (395118 hits)
#Поверхностное клонирование. (28535 hits)
#Использование компилируемых (prepared) запросов. (31781 hits)
#Валидация, динамическая проверка заполнения html форм. (211070 hits)
#Создание нестандартного (custom-ного) окна браузера. (36798 hits)
#Просмотр изображения во всплывающем окне. (90826 hits)
#Отслеживание изменений файла. (38972 hits)
#Перестановка фрагментов строки(или одномерного массива). (61913 hits)
#Глубокое полное клонирование. (36804 hits)
#Простая быстрая сортировка. (114561 hits)
#Случайный выбор нескольких несовпадающих значений из множества. (60174 hits)


Главная >> Каталог задач >> Паттерны >> Поведения >> Посетитель (Visitor)

Посетитель (Visitor)

Aвтор:
Дата:
Просмотров: 148301
реализации(java: 9шт...) +добавить

Имя

«Паттерн
Visitor»

Посетитель - паттерн поведения объектов, задающий стратегии обхода.

Условия, Задача, Назначение

Описывает операцию, которая должна быть выполнена над каждым объектом из некоторой произвольной структуры.

Позволяет определить и задать на выполнение новую операцию, не изменяя ни классы этих объектов, ни их структуры.

Мотивация

Рассмотрим компилятор, который представляет программу в виде абстрактного синтаксического дерева. Над такими деревьями он должен выполнять операции «статического семантического» анализа, например, проверять, что все переменные определены. Еще ему нужно генерировать код. Аналогично можно было бы определить операции контроля типов, оптимизации кода, анализа потока выполнения, проверки того, что каждой переменной было присвоено конкретное значение перед первым использованием, и т.д. Более того, абстрактные синтаксические деревья могли бы служить для красивой печати программы, реструктурирования кода и вычисления различных метрик программы.
В большинстве таких операций узлы дерева, представляющие операторы присваивания, следует рассматривать иначе, чем узлы, представляющие переменные и арифметические выражения. Поэтому один класс будет создан для операторов присваивания, другой - для доступа к переменным, третий – для арифметических выражений и т.д. Набор классов узлов, конечно, зависит от компилируемого языка, но не очень сильно.

На представленной диаграмме показана часть иерархии классов Node. Проблема здесь в том, что если раскидать все требуемые операции по классам различных узлов, то получится система, которую трудно понять, сопровождать и изменять. Вряд ли кто-нибудь разберется в программе, если код, отвечающий за проверку типов, будет перемешан с кодом, реализующим красивую печать или анализ потока выполнения. Кроме того, добавление любой новой операции потребует перекомпиляции всех классов. Оптимальный вариант - наличие возможности добавлять операции по отдельности и отсутствие зависимости классов узлов от применяемых к ним операций.
И того, и другого можно добиться, если поместить взаимосвязанные операции из каждого класса в отдельный объект, называемый посетителем, и передавать его элементам абстрактного синтаксического дерева по мере обхода. «Принимая» посетителя, элемент посылает ему запрос, в котором содержится, в частности, класс элемента. Кроме того, в запросе присутствует в виде аргумента и сам элемент. Посетителю в данной ситуации предстоит выполнить операцию над элементом, ту самую, которая наверняка находилась бы в классе элемента.
Например, компилятор, который не использует посетителей, мог бы проверить тип процедуры, вызвав операцию TypeCheck для представляющего ее абстрактного синтаксического дерева. Каждый узел дерева должен был реализовать операцию TypeCheck путем рекурсивного вызова ее же для своих компонентов (см. приведенную выше диаграмму классов). Если же компилятор проверяет тип процедуры посредством посетителей, то ему достаточно создать объект класса TypeCheckingVisitor и вызвать для дерева единую для всех узлов операцию Accept, передав ей этот объект в качестве аргумента. Каждый узел должен был реализовать Accept путем обращения к посетителю: узел, соответствующий оператору присваивания, вызывает операцию посетителя VisitAssignment, а узел, ссылающийся на переменную, -  операцию VisitVariableReference. To, что раньше было операцией TypeCheck в классе AssignmentNode, стало операцией VisitAssignment в классе TypeCheckingVisitor.
Чтобы посетители могли заниматься не только проверкой типов, нам необходим абстрактный класс NodeVisitor, являющийся родителем для всех посетителей синтаксического дерева. Приложение, которому нужно вычислять метрики программы, определило бы новые подклассы NodeVisitor-а, так что нам не пришлось бы добавлять зависящий от приложения код в классы узлов. Паттерн посетитель инкапсулирует операции, выполняемые на каждой фазе компиляции, в классе Visitor, ассоциированном с этой фазой:

И вот что происходит на стороне клиента:

Применяя паттерн посетитель, вы определяете две иерархии классов: одну для элементов, над которыми выполняется операция (иерархия Node), а другую – для посетителей, описывающих те операции, которые выполняются над элементами (иерархия NodeVisitor). Новая операция создается путем добавления подкласса в иерархию классов посетителей. До тех пор пока грамматика языка остается постоянной (то есть не добавляются новые подклассы Node), новую функциональность можно получить путем определения новых подклассов NodeVisitor.

Признаки применения, использования паттерна Посетитель (Visitor)

Используйте паттерн посетитель, когда:
  1. В структуре присутствуют объекты многих классов
    С различными интерфейсами и вы хотите выполнять над ними операции, зависящие от конкретных классов.
  2. Над объектами, входящими в состав структуры, надо выполнять разнообразные, не связанные между собой операции и вы не хотите «засорять» классы такими операциями. Посетитель позволяет объединить родственные операции, поместив их в один класс. Если структура объектов является общей для нескольких приложений, то паттерн посетитель позволит в каждое приложение включить только относящиеся к нему операции.
  3. Классы, устанавливающие структуру объектов, изменяются редко, но новые операции над этой структурой добавляются часто.
    При изменении классов, представленных в структуре, нужно будет переопределить интерфейсы всех посетителей, а это может вызвать затруднения. Поэтому если классы меняются достаточно часто, то, вероятно, лучше определить операции прямо в них.

Решение

Участники паттерна Посетитель (Visitor)

  1. Visitor (NodeVisitor) – посетитель.
    Объявляет операцию VisitXXX для каждого класса ConcreteElement в структуре объектов. Имя и сигнатура этой операции идентифицируют класс, который посылает посетителю запрос Visit-а. Имя метода позволяет посетителю определить, элемент какого конкретного класса он посещает, а ссылка на этот элемент передающая при вызове – обращаться к нему через его интерфейс.
  2. ConcreteVisitor (TypeCheckingVisitor) - конкретный посетитель.
    Реализует все операции, объявленные в классе Visitor. Каждая операция реализует фрагмент алгоритма, определенного только для класса соответствующего объекта в структуре. Класс ConcreteVisitor предоставляет контекст для этого алгоритма и сохраняет его локальное состояние. Часто в этом состоянии аккумулируются результаты, полученные в процессе обхода структуры.
  3. Element (Node) – элемент.
    Определяет операцию Accept, которая принимает посетителя в качестве аргумента.
  4. ConcreteElement (AssignmentNode, VariableRefNode) – конкретный элемент.
    Реализует операцию Accept, принимающую посетителя как аргумент. Реализует он ее каждый раз по-разному: а именно вызывает только тот Visit-метод, который для него предназначен.
  5. ObjectStructure (Program) - структура объектов.
    Перечисляет свои элементы.
    Предоставляет посетителю высокоуровневый интерфейс для посещения своих элементов.
    Может быть как составным объектом (см. паттерн компоновщик), так и коллекцией, например списком или множеством.

Схема использования паттерна Посетитель (Visitor)

Клиент, использующий паттерн посетитель, должен создать объект класса ConcreteVisitor, а затем обойти всю структуру, посетив каждый ее элемент.
При посещении элемента ConcreteElement вызывает операцию посетителя, соответствующую своему классу (типу). Элемент передает этой операции себя в качестве аргумента, чтобы посетитель мог при необходимости получить доступ к его состоянию.
На представленной диаграмме взаимодействий показаны отношения между объектом, структурой, посетителем и двумя элементами.

Вопросы, касающиеся реализации паттерна Посетитель (Visitor)

С каждым объектом структуры ассоциирован некий класс посетителя Visitor.
В этом абстрактном классе объявлены операции VisitConcreteElement для каждого конкретного класса ConcreteElement элементов, представленных в структуре. В каждой операции типа Visit аргумент объявлен как принадлежащий одному из классов ConcreteElement, так что посетитель может напрямую обращаться к интерфейсу этого класса. Классы ConcreteVisitor замещают операции Visit с целью реализации поведения посетителя для соответствующего класса ConcreteElement.
В C++ класс Visitor следовало бы объявить приблизительно так:
 Visitor [C++]  ссылка
  1. class Visitor {
  2. public:
  3. virtual void VisitElementA(ElementA*);
  4. virtual void VisitElementB(Elements*);
  5.  
  6. // и так далее для остальных конкретных элементов
  7. protected:
  8. Visitor() ;
  9. };
 
Каждый класс ConcreteElement реализует операцию Accept, которая вызывает соответствующую операцию VisitXXX посетителя для своего класса. Следовательно, вызываемая в конечном итоге операция зависит как от класса элемента, так и от класса посетителя. Поэтому можно было бы использовать перегрузку функций, чтобы дать этим операциям одно и то же простое имя, например Visit, а различать только типом передаваемого параметра. Имеются аргументы как за, так и против подобной перегрузки. С одной стороны, подчеркивается, что все операции выполняют однотипный анализ, хотя и с разными аргументами. С другой стороны, при этом читателю программы может быть не вполне понятно, что происходит при вызове. В общем все зависит от того, часто ли вы применяете перегрузку функций и легко ли всегда в ней ориентируетесь.
Конкретные элементы объявляются так:
 конкретные элементы обхода [C++]  ссылка
  1. class Element {
  2. public:
  3. virtual ~Element();
  4. virtual void Accept(Visitors) = 0;
  5. protected:
  6. Element();
  7. };
  8.  
  9. class ElementA : public Element {
  10. public:
  11. ElementA();
  12. virtual void Accept(Visitors v) { v.VisitElementA(this); }
  13. };
  14. class ElementB : public Element {
  15. public:
  16. ElementB();
  17. virtual void Accept(Visitors v) { v.VisitElementB(this); }
  18. };
 
Составной класс CompositeElement мог бы реализовать операцию Accept следующим образом:
 составной элемент [C++]  ссылка
  1. class CompositeElement : public Element {
  2. public:
  3. virtual void Accept(Visitors);
  4. private:
  5. List<Element*>* _children;
  6. };
  7. void CompositeElement::Accept (Visitors v) {
  8. ListIterator<Element*> i(_children);
  9. for (i.First(); !i.IsDone(); i.Next() {
  10. i .Currentltem()->Accept(v) ;
  11. }
  12. v.VisitCompositeElement(this);
  13. }
 
 
Переписав для разнообразия все вышеозвученное на Java получим:
 Visitor [java]  ссылка
  1. package visitor.ex;
  2.  
  3. public interface Visitor {
  4. void VisitElementA(ElementA el);
  5. void VisitElementB(ElementB el);
  6. void VisitCompositeElement(CompositeElement el);
  7. }
 элементы [java]  ссылка
  1. package visitor.ex;
  2.  
  3. public interface Element {
  4. void Accept(Visitor v);
  5. }
  6.  
  7. class ElementA implements Element {
  8.  
  9. public void Accept(Visitor v) {
  10. v.VisitElementA(this);
  11. }
  12. }
  13.  
  14. class ElementB implements Element {
  15.  
  16. public void Accept(Visitor v) {
  17. v.VisitElementB(this);
  18. }
  19.  
  20. }
  21.  
 составной элемент [java]  ссылка
  1. package visitor.ex;
  2.  
  3. import java.util.Iterator;
  4. import java.util.List;
  5.  
  6. public class CompositeElement implements Element {
  7. private List<Element> children;
  8.  
  9. public void Accept(Visitor v) {
  10. Iterator<Element> childIter = children.iterator();
  11. while (childIter.hasNext()) {
  12. childIter.next().Accept(v);
  13. }
  14. v.VisitCompositeElement(this);
  15. }
  16.  
  17. }
  18.  
 
При решении вопроса о применении паттерна посетитель часто возникают два спорных момента:
  1. Двойная диспетчеризация.
    По своей сути паттерн посетитель позволяет, не изменяя классы, добавлять в них новые операции. Достигает он этого с помощью приема, называемого двойной диспетчеризацией. Данная техника хорошо известна. Некоторые языки программирования (например, CLOS) поддерживают ее явно. Языки же вроде C++ и Smalltalk поддерживают только одинарную диспетчеризацию.
    Для определения того, какая операция будет выполнять запрос, в языках с одинарной диспетчеризацией неоходимы имя запроса и тип получателя. Например, то, какая операция будет вызвана для обработки запроса GenerateCode, зависит от типа объекта в узле, которому адресован запрос. В C++ вызов GenerateCode для экземпляра VariableRefNode приводит к вызову функции VariableRefNode::GenerateCode (генерирующей код обращения к переменной). Вызов же GenerateCode для узла класса AssignmentNode приводит к вызову функции AssignmentNode::GenerateCode (генерирующей код для оператора присваивания). Таким образом, выполняемая операция определяется одновременно видом запроса и типом получателя.
    Понятие «двойная диспетчеризация» означает, что выполняемая операция зависит от вида запроса и типов двух получателей. Accept – это операция с двойной диспетчеризацией. Ее семантика зависит от типов двух объектов: Visitor и Element. Двойная диспетчеризация позволяет посетителю запрашивать разные операции для каждого класса элемента (Если есть двойная диспетчеризация, то почему бы не быть тройной, четверной или диспетчеризации произвольной кратности? Двойная диспетчеризация - это просто частный случай множественной диспетчеризации, при которой выбираемая операция зависит от любого числа типов. CLOS как раз и поддерживает множественную диспетчеризацию.В языках с поддержкой двойной или множественной диспетчеризации необходимость в паттерне посетитель возникает гораздо реже.)
    Поэтому возникает необходимость в паттерне посетитель: выполняемая операция зависит и от типа посетителя, и от типа посещаемого элемента. Вместо статической привязки операций к интерфейсу класса Element мы можем консолидировать эти операции в классе Visitor и использовать Accept для привязки их во время выполнения. Расширение интерфейса класса Element сводится к определению нового подкласса Visitor, а не к модификации многих подклассов Element.
  2. Какой участник несет ответственность за обход структуры.
    Посетитель должен обойти каждый элемент структуры объектов. Вопрос в том, как туда попасть. Ответственность за обход можно возложить либо на саму структуру объектов, либо на посетителя либо на отдельный объект-итератор (см. паттерн итератор).
    Чаще всего структура объектов отвечает за обход. Коллекция просто обходит все свои элементы, вызывая для каждого операцию Accept. Составной объект обычно обходит самого себя, «заставляя» операцию Accept посетить потомков текущего элемента и рекурсивно вызвать Accept для каждого из них.
    Другое решение - воспользоваться итератором для посещения элементов.
    Можно применить внутренний или внешний итератор, в зависимости от того, что доступно и более эффективно. Поскольку внутренние итераторы реализуются самой структурой объектов, то работа с ними во многом напоминает предыдущее решение, когда за обход отвечает структура.
    Основное различие заключается в том, что внутренний итератор не приводит к двойной диспетчеризации: он вызывает операцию посетителя с элементом в качестве аргумента, а не операцию элемента с посетителем в качестве аргумента. Однако использовать паттерн посетитель с внутренним итератором легко в том случае, когда операция посетителя вызывает операцию элемента без рекурсии.
    Можно даже поместить алгоритм обхода в посетитель, хотя закончится это дублированием кода обхода в каждом классе ConcreteVisitor для каждого агрегата ConcreteElement. Основная причина такого решения – необходимость реализовать особо сложную стратегию обхода, зависящую от результатов операций над объектами структуры.

Результаты

Некоторые достоинства и недостатки паттерна посетитель:
  1. Упрощает добавление новых операций.
    С помощью посетителей легко добавлять операции, зависящие от компонентов сложных объектов. Для определения новой операции над структурой объектов достаточно просто ввести нового посетителя. Напротив, если функциональность распределена по нескольким классам, то для определения новой операции придется изменить каждый класс.
  2. Объединяет родственные операции и отсекает те, которые не имеют к ним отношения.
    Родственное поведение не разносится по всем классам, присутствующим в структуре объектов, оно локализовано в посетителе. Не связанные друг с другом функции распределяются по отдельным подклассам класса Visitor. Это способствует упрощению как классов, определяющих элементы, так и алгоритмов, инкапсулированных в посетителях. Все относящиеся к алгоритму структуры данных можно скрыть в посетителе.
  3. Добавление новых классов ConcreteElement затруднено.
    Паттерн посетитель усложняет добавление новых подклассов класса Element. Каждый новый конкретный элемент требует объявления новой абстрактной операции в классе Visitor, которую нужно реализовать в каждом из существующих на данный момент классов ConcreteVisitor. Иногда большинство конкретных посетителей могут унаследовать операцию по умолчанию, предоставляемую классом Visitor, но это, скорее, исключение, чем правило.
    Поэтому при решении вопроса о том, стоит ли использовать паттерн посетитель, нужно прежде всего посмотреть, что будет изменяться чаще: алгоритм, применяемый к объектам структуры, или классы объектов, составляющих эту структуру. Вполне вероятно, что сопровождать иерархию классов Visitor будет нелегко, если новые классы ConcreteElement добавляются часто. В таких случаях проще определить операции прямо в классах, представленных в структуре. Если же иерархия классов Element стабильна, но постоянно расширяется набор операций или модифицируются алгоритмы, то паттерн посетитель поможет лучше управлять такими изменениями.
  4. Посещение различных иерархий классов.
    Итератор может посещать объекты структуры по мере ее обхода, вызывая операции объектов. Но итератор не способен работать со структурами, состоящими из объектов разных типов. Так, интерфейс класса Iterator, может всего лишь получить доступ к объектам типа Item:
     итератор для доступа к элементам [C++]  ссылка
    1. template <class Item>
    2. class Iterator {
    3. // ...
    4. Item CurrentltemO const;
    5. };

    Отсюда следует, что все элементы, которые итератор может посетить, должны иметь общий родительский класс Item.
    У посетителя таких ограничений нет. Ему разрешено посещать объекты, не имеющие общего родительского класса. В интерфейс класса Visitor можно добавить операции для объектов любого типа. Например, в следующем объявлении:
     наличие операций любого типа [C++]  ссылка
    1. class Visitor {
    2. public:
    3. // ...
    4. void VisitMyType(MyType*);
    5. void VisitYourType(YourType*);
    6. };

    классы МуТуре и YourType необязательно должны быть связаны отношением наследования.
  5. Аккумулирование состояния.
    Посетители могут аккумулировать информацию о состоянии при посещении объектов структуры. Если не использовать этот паттерн, состояние придется передавать в виде дополнительных аргументов операций, выполняющих обход, или хранить в глобальных переменных.
  6. Нарушение инкапсуляции.
    Применение посетителей подразумевает, что у класса ConcreteElement достаточно развитый интерфейс для того, чтобы посетители могли справиться со своей работой. Поэтому при использовании данного паттерна приходится предоставлять много открытых операций для доступа к внутреннему состоянию элементов, что ставит под угрозу инкапсуляцию.

Пример

Рассмотрим пример автоматизации ассортимента товаров в магазине компьютерных комплектующих.
Поскольку посетители обычно ассоциируются с составными объектами, то для иллюстрации паттерна посетитель мы воспользуемся классами Equipment/CompositeEquipment, спроектированные в соответствии с паттерном компоновщиком. Для определения операций, создающих инвентарную опись материалов и вычисляющих полную стоимость агрегата, нам понадобится и паттерн посетитель.

Для поддержки посетителя в класс Equipment добавляется операция Accept: Equipment.

Класс составного оборудования, которое включает в себя любое количество внутренних частей (объектов класса Equipment) будет иметь вид: CompositeEquipment.
 
Операции класса Equipment возвращают такие атрибуты единицы оборудования, как потребляемую мощность, стоимость и другие. В подклассах эти операции переопределены в  соответствии с конкретными типами оборудования (системники, дисководы, электронные платы).
Определим интерфейс посетителя каждого товара нашего магазина: EquipmentVisitor.
 
Далее реализуем некоторые конкретные классы товаров (подклассы класса Equipment) нашего магазина. Все они определяют операцию Accept практически одинаково. Она вызывает операцию EquipmentVisitor-а, соответствующую тому классу, который получил запрос Accept: Card, FloppyDisk.
 
Виды оборудования, которые содержат другое оборудование (в частности, подклассы CompositeEquipment в терминологии паттерна компоновщик), реализуют Accept путем обхода своих потомков и вызова Accept для каждого из них.
Затем, как обычно, вызывается операция Visit. Например, в случае системного блока Chassis получим: Chassis.
 
Подклассы EquipmentVisitor определяют конкретные алгоритмы, применяемые к структуре оборудования. Так, PricingVisitor вычисляет стоимость всего ассортимента, для чего суммирует нетто-цены простых компонентов (например, гибкие диски) и цену со скидкой составных компонентов (например, системные блоки): PricingVisitor.
 
Таким образом, посетитель PricingVisitor подсчитает полную стоимость всех узлов конструкции. Заметим, что PricingVisitor выбирает стратегию вычисления цены в зависимости от класса оборудования, для чего вызывает соответствующую функцию-член. Особенно важно то, что для оценки конструкции можно выбрать другую стратегию, просто поменяв класс PricingVisitor.
Посетитель InventoryVisitor подсчитывает итоговое количество каждого вида оборудования во всей конструкции: InventoryVisitor.
 
И вот как все это вместе работает: Client.
 
Т.е. заполняем ассортимент товаров, и применяем имеющихся посетителей: для подсчета полной стоимости всех товаров магазина, и для их описи.

Известные применения паттерна Посетитель (Visitor)

В компиляторе Smalltalk-80 имеется класс посетителя, который называется ProgramNodeEnumerator. В основном он применяется в алгоритмах анализа исходного текста программы и не используется ни для генерации кода, ни для красивой печати, хотя мог бы.
IRIS Inventor - это библиотека для разработки приложений трехмерной графики. Библиотека представляет собой трехмерную сцену в виде иерархии узлов, каждый из которых соответствует либо геометрическому объекту, либо его атрибуту. Для операций типа изображения сцены или обработки события ввода необходимо по-разному обходить эту иерархию. В Inventor для этого служат посетители, которые называются действиями (actions). Есть различные посетители для изображения, обработки событий, поиска, сохранения и определения ограничивающих прямоугольников.
Чтобы упростить добавление новых узлов, в библиотеке Inventor реализована схема двойной диспетчеризации на C++. Для этого служит информация о типе, доступная во время выполнения, и двумерная таблица, строки которой представляют посетителей, а колонки - классы узлов. В каждой ячейке хранится указатель на функцию, связанную с парой посетитель-класс узла.

Марк Линтон (Mark Linton) ввел термин «посетитель» (Visitor) в спецификацию библиотеки для построения приложений X Consortium's Fresco Application Toolkit.

Родственные паттерны

Компоновщик: посетители могут использоваться для выполнения операции над всеми объектами структуры, определенной с помощью паттерна компоновщик.

Интерпретатор: посетитель может использоваться для выполнения интерпретации.

Реализации:

java(9)   +добавить

1) Equipment.java на java, code #529[автор:this]
2) CompositeEquipment.java на java, code #530[автор:this]
3) EquipmentVisitor.java на java, code #531[автор:this]
4) Card.java на java, code #532[автор:this]
5) FloppyDisk.java на java, code #533[автор:this]
6) Chassis.java на java, code #534[автор:this]
7) PricingVisitor.java на java, code #535[автор:this]
8) InventoryVisitor.java на java, code #536[автор:this]
9) Client.java на java, code #537[автор:this]