Паттерн Посетитель

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

      using System;
using System.IO;

namespace VisitorPatternDemo.Tree
{
  publicabstractclass TreeNodeBase
  {
    privatereadonlystring _name;

    protected TreeNodeBase(string name)
    {
      if (name == null)
        thrownew ArgumentNullException("name");
      _name = name;
    }

    publicstring Name
    {
      get { return _name; }
    }

    publicoverridestring ToString()
    {
      return Name;
    }

    publicabstractvoid Print(TextWriter writer);
  }
}


using System.IO;

namespace VisitorPatternDemo.Tree
{
  publicclass Type1Node : TreeNodeBase
  {
    public Type1Node(string name) : base(name)
    {
    }

    publicoverridevoid Print(TextWriter writer)
    {
      writer.WriteLine(Name + " : Type1");
    }
  }
}

using System.IO;

namespace VisitorPatternDemo.Tree
{
  publicclass Type3Node : TreeNodeBase
  {
    public Type3Node(string name) : base(name)
    {
    }

    publicoverridevoid Print(TextWriter writer)
    {
      writer.WriteLine(Name + " : Type3");
    }
  }
}

using System;
using System.Collections.Generic;
using System.IO;

namespace VisitorPatternDemo.Tree
{
  publicclass Type2Node : TreeNodeBase
  {
    privatereadonly IList<Type3Node> _type3Nodes;

    public Type2Node(string name, Type3Node[] type3Nodes) : base(name)
    {
      _type3Nodes = Array.AsReadOnly(type3Nodes);
    }

    public IList<Type3Node> Type3Nodes
    {
      get { return _type3Nodes; }
    }

    publicoverridevoid Print(TextWriter writer)
    {
      writer.WriteLine(Name + " : Type2");
      foreach (Type3Node node in Type3Nodes)
        node.Print(writer);
    }
  }
}

using System;
using System.Collections.Generic;
using System.IO;

namespace VisitorPatternDemo.Tree
{
  publicclass RootNode : TreeNodeBase
  {
    privatereadonly IList<Type1Node> _type1Nodes;
    privatereadonly IList<Type2Node> _type2Nodes;

    public RootNode(Type1Node[] type1Nodes, Type2Node[] type2Nodes) : base("Root")
    {
      _type1Nodes = Array.AsReadOnly(type1Nodes);
      _type2Nodes = Array.AsReadOnly(type2Nodes);
    }

    public IList<Type1Node> Type1Nodes
    {
      get { return _type1Nodes; }
    }

    public IList<Type2Node> Type2Nodes
    {
      get { return _type2Nodes; }
    }

    publicoverridevoid Print(TextWriter writer)
    {
      writer.WriteLine(Name + " : Root");
      foreach (Type1Node node in Type1Nodes)
        node.Print(writer);
      foreach (Type2Node node in Type2Nodes)
        node.Print(writer);
    }
  }
}

using System;
using VisitorPatternDemo.Tree;

namespace VisitorPatternDemo
{
  internalclass Program
  {
    privatestatic TreeNodeBase CreateTree()
    {
      returnnew RootNode(
        new Type1Node[] 
{
          new Type1Node("T11"),
          new Type1Node("T12"),
          new Type1Node("T13")
        },
        new Type2Node[] 
{
          new Type2Node("T21",
            new Type3Node[]
{
              new Type3Node("T311"),
              new Type3Node("T312"),
            }
          ),
          new Type2Node("T22",
            new Type3Node[]
{
              new Type3Node("T321"),
              new Type3Node("T322"),
            }
          )
        }
      );
    }
    
    privatestaticvoid Main()
    {
      TreeNodeBase tree = CreateTree();
      tree.Print(Console.Out);

      Console.Read();
    }
  }
}

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

Одним из вариантов решения проблемы высокой связности в данном случае является паттерн Посетитель.

Паттерн Посетитель

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

      namespace VisitorPatternDemo
{
  publicinterface IVisitor
  {
    void VisitRoot(RootNode node);
    void VisitType1(Type1Node node);
    void VisitType2(Type2Node node);
    void VisitType3(Type3Node node);
  }
}

publicabstractclass TreeNodeBase
{
  // ...publicabstractvoid AcceptVisitor(IVisitor visitor);
}


publicclass RootNode : TreeNodeBase
{
  // ...publicoverridevoid AcceptVisitor(IVisitor visitor)
  {
    visitor.VisitRoot(this);
  }
}

publicclass Type1Node : TreeNodeBase
{
  /// ...publicoverridevoid AcceptVisitor(IVisitor visitor)
  {
    visitor.VisitType1(this);
  }
}

publicclass Type2Node : TreeNodeBase
{
  /// ...publicoverridevoid AcceptVisitor(IVisitor visitor)
  {
    visitor.VisitType2(this);
  }
}

publicclass Type3Node : TreeNodeBase
{
  /// ...publicoverridevoid AcceptVisitor(IVisitor visitor)
  {
    visitor.VisitType3(this);
  }
}

Теперь для того, чтобы обеспечить работу алгоритма по объектной структуре, достаточно реализовать интерфейс IVisitor.

      using System.IO;
using VisitorPatternDemo.Tree;

namespace VisitorPatternDemo
{
  publicclass PrintVisitor : IVisitor
  {
    privatereadonly TextWriter _writer;

    private PrintVisitor(TextWriter writer)
    {
      _writer = writer;
    }

    publicstaticvoid Print(TreeNodeBase tree, TextWriter writer)
    {
      tree.AcceptVisitor(new PrintVisitor(writer));
    }

    void IVisitor.VisitRoot(RootNode rootNode)
    {
      _writer.WriteLine(rootNode.Name + " : Root");
      foreach (Type1Node node in rootNode.Type1Nodes)
        node.AcceptVisitor(this);
      foreach (Type2Node node in rootNode.Type2Nodes)
        node.AcceptVisitor(this);
    }

    void IVisitor.VisitType1(Type1Node node)
    {
      _writer.WriteLine(node.Name + " : Type1");
    }

    void IVisitor.VisitType2(Type2Node node)
    {
      _writer.WriteLine(node.Name + " : Type2");
      foreach (Type3Node t3Node in node.Type3Nodes)
        t3Node.AcceptVisitor(this);
    }

    void IVisitor.VisitType3(Type3Node node)
    {
      _writer.WriteLine(node.Name + " : Type3");
    }
  }
}

Если алгоритм обхода структуры всегда один и тот же, код обхода дерева (foreach в примере) можно перенести в метод Accept. При этом в коде реализации посетителя осуществлять обход не нужно. Однако это снижает гибкость кода, так как другой способ обхода использовать уже не удастся.

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

      using VisitorPatternDemo.Tree;

namespace VisitorPatternDemo
{
  publicabstractclass VisitorBase : IVisitor
  {
    protected VisitorBase()
    {
    }

    protectedabstractvoid DoVisitRoot(RootNode node);
    protectedabstractvoid DoVisitType1(Type1Node node);
    protectedabstractvoid DoVisitType2(Type2Node node);
    protectedabstractvoid DoVisitType3(Type3Node node);

    void IVisitor.VisitRoot(RootNode node)
    {
      DoVisitRoot(node);
      foreach (Type1Node childNode in node.Type1Nodes)
        childNode.AcceptVisitor(this);
      foreach (Type2Node childNode in node.Type2Nodes)
        childNode.AcceptVisitor(this);
    }

    void IVisitor.VisitType1(Type1Node node)
    {
      DoVisitType1(node);
    }

    void IVisitor.VisitType2(Type2Node node)
    {
      DoVisitType2(node);
      foreach (Type3Node childNode in node.Type3Nodes)
        childNode.AcceptVisitor(this);
    }

    void IVisitor.VisitType3(Type3Node node)
    {
      DoVisitType3(node);
    }
  }
}

using System;
using System.IO;
using VisitorPatternDemo.Tree;

namespace VisitorPatternDemo
{
  publicclass PrintVisitor2 : VisitorBase
  {
    privatereadonly TextWriter _writer;

    private PrintVisitor2(TextWriter writer)
    {
      _writer = writer;
    }

    publicstaticvoid Print(TreeNodeBase tree, TextWriter writer)
    {
      tree.AcceptVisitor(new PrintVisitor2(writer));
    }

    protectedoverridevoid DoVisitRoot(RootNode node)
    {
      _writer.WriteLine(node.Name + " : Root");
    }

    protectedoverridevoid DoVisitType1(Type1Node node)
    {
      _writer.WriteLine(node.Name + " : Type1");
    }

    protectedoverridevoid DoVisitType2(Type2Node node)
    {
      _writer.WriteLine(node.Name + " : Type2");
    }

    protectedoverridevoid DoVisitType3(Type3Node node)
    {
      _writer.WriteLine(node.Name + " : Type3");
    }
  }
}

Использование перегрузки методов

В языках, поддерживающих перегрузку методов, ее можно использовать для упрощения реализации метода Accept .

Для использования этой техники необходимо, чтобы все методы посетителя назывались одинаково и различались лишь типом параметра. В этом случае код метода Accept будет одинаковым. Компилятор при компиляции сам выберет необходимый метод.

      using VisitorPatternDemo.Tree;

namespace VisitorPatternDemo
{
  publicinterface IDDVisitor
  {
    void Visit(RootNode node);
    void Visit(Type1Node node);
    void Visit(Type2Node node);
    void Visit(Type3Node node);
  }
}

publicabstractclass TreeNodeBase
{
  // ...publicabstractvoid AcceptVisitor(IDDVisitor visitor);
}

publicclass RootNode : TreeNodeBase
{
  // ...  publicoverridevoid AcceptVisitor(IDDVisitor visitor)
  {
    visitor.Visit(this);
  }
}

publicclass Type1Node : TreeNodeBase
{
  // ...  publicoverridevoid AcceptVisitor(IDDVisitor visitor)
  {
    visitor.Visit(this);
  }
}

publicclass Type2Node : TreeNodeBase
{
  // ...  publicoverridevoid AcceptVisitor(IDDVisitor visitor)
  {
    visitor.Visit(this);
  }
}

publicclass Type3Node : TreeNodeBase
{
  // ...  publicoverridevoid AcceptVisitor(IDDVisitor visitor)
  {
    visitor.Visit(this);
  }
}

Этот прием позволяет устранить ошибки, связанные с вызовом неверного метода в методе Accept.

Передача параметров

В некоторых случаях в методы посетителя требуется передать параметр. Для этого необходимо в методы Visit и AcceptVisitor добавить параметр – контекст вызова. Если язык поддерживает обобщенное программирование, то этот контекст можно сделать статически типизированным.

      using VisitorPatternDemo.Tree;

namespace VisitorPatternDemo
{
  publicinterface IContextVisitor<C>
  {
    void Visit(C context, RootNode node);
    void Visit(C context, Type1Node node);
    void Visit(C context, Type2Node node);
    void Visit(C context, Type3Node node);
  }
}

publicabstractclass TreeNodeBase
{
  //...publicabstractvoid AcceptVisitor<C>(C context, IContextVisitor<C> visitor);
}

publicclass RootNode : TreeNodeBase
{
  // ...publicoverridevoid AcceptVisitor<C>(C context, IContextVisitor<C> visitor)
  {
    visitor.Visit(context, this);
  }
}

using System.IO;
using VisitorPatternDemo.Tree;

namespace VisitorPatternDemo
{
  publicclass PrintContextVisitor : IContextVisitor<int>
  {
    privatereadonly TextWriter _writer;

    private PrintContextVisitor(TextWriter writer)
    {
      _writer = writer;
    }

    publicstaticvoid Print(TreeNodeBase tree, TextWriter writer)
    {
      tree.AcceptVisitor(0, new PrintContextVisitor(writer));
    }

    void IContextVisitor<int>.Visit(int context, RootNode rootNode)
    {
      _writer.WriteLine(newstring(' ', context) + rootNode.Name + " : Root");
      foreach (Type1Node node in rootNode.Type1Nodes)
        node.AcceptVisitor(context + 1, this);
      foreach (Type2Node node in rootNode.Type2Nodes)
        node.AcceptVisitor(context + 1, this);
    }

    void IContextVisitor<int>.Visit(int context, Type1Node node)
    {
      _writer.WriteLine(newstring(' ', context) + node.Name + " : Type1");
    }

    void IContextVisitor<int>.Visit(int context, Type2Node node)
    {
      _writer.WriteLine(newstring(' ', context) + node.Name + " : Type2");
      foreach (Type3Node t3Node in node.Type3Nodes)
        t3Node.AcceptVisitor(context + 1, this);
    }

    void IContextVisitor<int>.Visit(int context, Type3Node node)
    {
      _writer.WriteLine(newstring(' ', context) + node.Name + " : Type3");
    }
  }
}

Реализация посетителя при помощи функторов

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

В .NET имеется специализированный тип – делегат, реализующий функциональность функторов.

Идея использования функциональных объектов заключается в том, что мы во время выполнения строим карту (map) типов на эти объекты и затем, вместо вызова Accept, используем эту карту. С использованием механизма рефлексии такую карту можно построить автоматически, на основании интерфейса посетителя.

      using System;
using System.Collections.Generic;
using System.Reflection;

namespace VisitorPatternDemo
{
  publicclass FuncVisitHelper<V, C>
  {
    internaldelegatevoid VisitDelegate<I>(C context, I item);
    
    privatereadonly IDictionary<Type, Delegate> _map;

    public FuncVisitHelper(V visitor)
    {
      _map = BuildMap(visitor);
    }

    private IDictionary<Type, Delegate> BuildMap(V visitor)
    {
      Dictionary<Type, Delegate> map = new Dictionary<Type, Delegate>();
      foreach (MethodInfo mi intypeof (V).GetMethods())
      {
        ParameterInfo[] pis = mi.GetParameters();
        if (pis.Length != 2)
          thrownew ArgumentException(string.Format(
            "Метод '{0}' должен иметь 2 параметра", mi.Name));
        map.Add(pis[1].ParameterType,
          Delegate.CreateDelegate(
            typeof (VisitDelegate<>).MakeGenericType(
              typeof (V),
              typeof (C),
              pis[1].ParameterType),
            visitor,
            mi));
      }
      return map;
    }

    publicvoid AcceptVisitor<I>(C context, I item)
    {
      Delegate del;
      if (!_map.TryGetValue(typeof (I), out del))
        thrownew ApplicationException(string.Format(
          "Тип '{0}' не содержится в интерфейсе посетителя '{1}'",
          typeof(I), typeof(V)));
      ((VisitDelegate<I>)del)(context, item);
    }
  }
}


using System.IO;
using VisitorPatternDemo.Tree;

namespace VisitorPatternDemo
{
  publicclass PrintFuncVisitor : IContextVisitor<int>
  {
    privatereadonly TextWriter _writer;
    privatereadonly FuncVisitHelper<IContextVisitor<int>, int> _helper;

    private PrintFuncVisitor(TextWriter writer)
    {
      _writer = writer;
      _helper = new FuncVisitHelper<IContextVisitor<int>, int>(this);
    }

    publicstaticvoid Print(TreeNodeBase tree, TextWriter writer)
    {
      new PrintFuncVisitor(writer)._helper.AcceptVisitor<RootNode>(
0, (RootNode)tree);
    }

    void IContextVisitor<int>.Visit(int context, RootNode rootNode)
    {
      _writer.WriteLine(newstring(' ', context) + rootNode.Name + " : Root");
      foreach (Type1Node node in rootNode.Type1Nodes)
        _helper.AcceptVisitor(context + 1, node);
      foreach (Type2Node node in rootNode.Type2Nodes)
        _helper.AcceptVisitor(context + 1, node);
    }

    void IContextVisitor<int>.Visit(int context, Type1Node node)
    {
      _writer.WriteLine(newstring(' ', context) + node.Name + " : Type1");
    }

    void IContextVisitor<int>.Visit(int context, Type2Node node)
    {
      _writer.WriteLine(newstring(' ', context) + node.Name + " : Type2");
      foreach (Type3Node t3Node in node.Type3Nodes)
        _helper.AcceptVisitor(context + 1, t3Node);
    }

    void IContextVisitor<int>.Visit(int context, Type3Node node)
    {
      _writer.WriteLine(newstring(' ', context) + node.Name + " : Type3");
    }
  }
}

Для ускорения работы такого посетителя крайне рекомендуется кэшировать карты в статическом контексте. Еще один вариант повышения производительности – замена карты с делегатами на динамическую кодогенерацию.

Паттерн Посетитель

Использование паттерна Посетитель в языке C#

Автор: Андрей Корявченко
The RSDN Group
Источник: RSDN Magazine #3-2006

Опубликовано: 06.12.2006
Исправлено: 10.12.2016
Версия текста: 1.0

Для чего это нужно