Odwiedzający

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Odwiedzający (wizytator) – wzorzec projektowy, którego zadaniem jest odseparowanie algorytmu od struktury obiektowej na której operuje. Praktycznym rezultatem tego odseparowania jest możliwość dodawania nowych operacji do aktualnych struktur obiektów bez konieczności ich modyfikacji.

Wstęp[edytuj | edytuj kod]

We wzorcu projektowym wprowadzony zostaje nowy typ obiektu Wizytator, którego zadaniem jest "odwiedzenie" każdego elementu w danej strukturze obiektów i wykonanie na nim konkretnych działań. Różne implementacje wizytatorów, mogą wykonywać różne zadania, rozszerzając funkcjonalność struktury elementów, bez ich wewnętrznej modyfikacji.

Struktura wzorca[edytuj | edytuj kod]

Diagram UML dla wzorca projektowego "Odwiedzający"

Idea wzorca polega na stworzeniu interfejsu odwiedzającego (Visitor) zawierającego metody wirtualne Visit, dedykowane dla każdej z implementacji elementów (dziedziczących po klasie Element) w zadanej strukturze obiektów.

Każdy odwiedzający jest "przyjmowany" przez dany element poprzez metodę Accept - dla poszczególnych implementacji obiektów Element, wołane są odpowiednie metody Visit w interfejsie Visitor odwiedzającego.

Różne implementacje interfejsu Visitor mogą zawierać (hermetyzować) różne funkcjonalności dla całych struktur danych (składających się z obiektów Element). Obiekty tego typu reprezentują algorytmy wykonujące zadane czynności na każdym obiekcie osobno.

Dla zbioru obiektów odwiedzanych, metoda Accept powinna być wywoływana w odpowiedniej kolejności, gwarantując, iż każdy element zostanie odwiedzony w odpowiednim momencie. Przykładowo, wizytator odwiedzający węzły w drzewie, powinien być akceptowany w kolejnych potomkach każdego z węzłów, zaś wizytator odwiedzający listę, może być wołany kolejno dla poszczególnych elementów.

Przykładowe zastosowanie[edytuj | edytuj kod]

Wzorzec wizytatora może być zastosowany przy implementacji drzewa wyprowadzenia w parserach lub kompilatorach. Niech analizator składniowy zwróci strukturę danych, będącą drzewem wyprowadzenia danego na wejście wyrażenia matematycznego. Drzewo to symbolizuje budowę semantyczną pewnej formuły matematycznej i składa się z dwóch rodzajów węzłów:

  • ArgumentNode - stała wartość numeryczna w wyrażeniu, np. "1.0".
  • OperatorNode - operator binarny w wyrażeniu; przyjmuje za argumenty prawy i lewy węzeł potomny, np. "1.0 + 2.0".

Aby wykonać szereg operacji na całym drzewie, takich jak np. translacja wyrażenia do Odwrotnej Notacji Polskiej lub kalkulacja wyrażenia, trzeba dla każdego z węzłów drzewa zaimplementować metody wykonujące powyższe zadania. Utrzymanie i stworzenie tak rozwiniętego kodu dla każdej z klas reprezentujących węzeł w drzewie może być dość skomplikowane. Aby uniknąć takich sytuacji, można wykorzystać wzorzec wizytatora.

Niech obiekty będące węzłami w drzewie, będą zawierały metodę Accept, w treści której odwiedzający będzie przyjmowany kolejno w lewym i prawym dziecku oraz w samym węźle. Cała funkcjonalność wykonywana na drzewie, może być zaimplementowana w różnych wizytatorach (implementujących interfejs Visitor):

  • PostfixPrintVisitor - wizytator odpowiedzialny za przetłumaczenie wyrażenia matematycznego do postaci Odwrotnej Notacji Polskiej.
  • CalculationVisitor - wizytator odpowiedzialny za obliczenie wyrażenia matematycznego. Wizytator używa stosu zawierającego wartości numeryczne; na stosie odkładane są obliczone wyniki dla każdego z węzłów reprezentującego operacje matematyczną.

Poniżej zamieszczono przykładowy kod w C++ obrazujący działanie opisanych wizytatorów:

struct Node
{
    Node *Left, *Right;
 
    virtual void Accept( Visitor *v ) = 0;
};
 
struct ArgumentNode : public Node
{
    double Argument;
 
    virtual void Accept( Visitor *v )
    {
        v->VisitArgumentNode( this );
    }
};
 
struct OperatorNode : public Node
{
    char Operator;
 
    virtual void Accept( Visitor *v )
    {
        if ( Left != NULL ) 
            Left->Accept( v );
        if ( Right != NULL )
            Right->Accept( v );
 
        v->VisitOperatorNode( this );
    }
};
 
struct Visitor
{
    virtual void VisitArgumentNode( ArgumentNode *n ) = 0;
    virtual void VisitOperatorNode( OperatorNode *n ) = 0;
};
 
struct PostfixPrintVisitor : public Visitor
{
    String Output;
 
    virtual void VisitArgumentNode( ArgumentNode *n )
    {
        Output += ToString( n->Argument );
    }
 
    virtual void VisitOperatorNode( OperatorNode *n )
    {
        Output += n->Operator;
    }
};
 
struct CalculationVisitor : public Visitor
{
    stack<Numeric> NumericStack;
 
    virtual void VisitArgumentNode( ArgumentNode *n )
    {
        NumericStack.push( n->Argument );
    }
 
    virtual void VisitOperatorNode( OperatorNode *n )
    {
        Numeric b = NumericStack.top();
        NumericStack.pop();
 
        Numeric a = NumericStack.top();
        NumericStack.pop();
 
        switch ( n->Operator )
        {
        case '+':
            NumericStack.push( a + b );			    
            break;
        case '-':
            NumericStack.push( a - b );			    
            break;
        case '*':
            NumericStack.push( a * b );			    
            break;
        case '/':
            NumericStack.push( a / b );			    
            break;
        }
    }
};
 
 
Node *root = GetParseTree();
 
PostfixPrintVisitor *printVisitor = new PostfixPrintVisitor;
root->Accept( printVisitor );
Print( "Postfix notation: " + printVisitor->Output );
 
CalculationVisitor *calcVisitor = new CalculationVisitor;
root->Accept( calcVisitor );
Print( "Result: " + calcVisitor->NumericStack.top() );

Zobacz też[edytuj | edytuj kod]

Wikimedia Commons

Bibliografia[edytuj | edytuj kod]

  1. Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides, Design Patterns: Elements of Reusable Object-Oriented Software, Addison-Wesley Longman Publishing Co. Inc., 1994.