Mão na massa: Visitor

Problema:

É comum em projetos, onde você precisa criar sua própria estrutura de dados, que sejam necessários implementar várias operações sobre este conjunto de dados. Geralmente, esta responsabilidade é delegada para a própria classe que representa a estrutura.

Para discutirmos melhor, suponha que em um projeto você precisa lidar com uma estrutura de dados muito complexa, uma árvore binária por exemplo (tá, não é tão complexo mas serve pro exemplo). É comum que sejam implementados métodos para percorrer a árvore, como por exemplo: in-order, pre-order e post-order. [2]

O problema em implementar estes métodos diretamente na classe que representa a árvore é que é preciso ter um alto nível de certeza de que estas operações não mudarão, ou que serão utilizadas apenas nesta estrutura, pois o custo para realizar alterações seria muito grande, uma vez que o sistema dependerá da definição desta classe.

Outro problema é que, várias outras estruturas de dados vão utilizar uma abordagem semelhante. Por exemplo, caso seja implementado uma árvore AVL, que utiliza os mesmo dados e as mesmas operações de percurso, não seria possível reutilizar este método (reutilizar NÃO É ctrl+c ctrl+v!).

Vejamos então um pouco sobre o padrão Visitor, que vai nos ajudar bastante a resolver este problema.

Visitor

Como de costume, vamos a intenção do padrão:

“Representar uma operação a ser executada nos elementos de uma estrutura de objetos. Visitor permite definir uma nova operação sem mudar as classes dos elementos sobre os quais opera.” [1]

Pela intenção já é possível ver como o padrão vai nos ajudar. A sua ideia é separar as operações que serão executadas em determinada estrutura de sua representação. Assim, incluir ou remover operações não terá nenhum efeito sobre a interface da estrutura, permitindo que o resto do sistema funcione sem depender de operações específicas.

Vamos então começar definindo a estrutura de dados a ser utilizada. A seguinte classe representa o nó da árvore:

public class No {
	protected int chave;
	No esquerdo, direito;

	public No(int chave) {
		this.chave = chave;
		esquerdo = null;
		direito = null;
	}

	public String toString() {
		return String.valueOf(chave);
	}

	public int getChave() {
		return chave;
	}

	public No getEsquerdo() {
		return esquerdo;
	}

	public void setEsquerdo(No esquerdo) {
		this.esquerdo = esquerdo;
	}

	public No getDireito() {
		return direito;
	}

	public void setDireito(No direito) {
		this.direito = direito;
	}

}

Definimos então o nó básico da árvore, que contém a chave e os nós esquerdo e direito. Além disso o método “toString()” permite que a estrutura seja exibida na tela com o sysout. Agora vamos ver a estrutura árvore, que vai manter todos estes elementos.

public class ArvoreBinaria {
	No raiz;
	int quantidadeDeElementos;

	public ArvoreBinaria(int chaveRaiz) {
		raiz = new No(chaveRaiz);
		quantidadeDeElementos = 0;
	}

	public void inserir(int chave) {
		...
	}

	public void remover(int chave){
		...
	}

	public void buscar(int chave){
		...
	}

	public void aceitarVisitante(ArvoreVisitor visitor) {
		visitor.visitar(raiz);
	}
}

A estrutura árvore vai então possuir o nó raiz da árvore e algumas outras informações sobre a árvore. Omiti a implementação dos métodos da árvore para simplificar o exemplo. O detalhe importante desta classe é o método “aceitarVisitante()”, ele recebe um objeto ArvoreVisitor e passa a sua raiz para ele. Ai começa a implementação do padrão de verdade.

A estrutura de dados vai possuir um método que recebe um objeto visitante. Deste método ela vai chamar o método visitar, do objeto visitante, e vai passar os seus dados para o objeto visitante. Dai em diante, o objeto visitante vai poder realizar as operações necessárias. Vamos então começar com a implementação de ArvoreVisitor:

public interface ArvoreVisitor {

	void visitar(No no);

}

Esta classe vai apenas definir a interface de visita de um nó. Todas as operações vão receber um objeto No e a partir dai vão implementar suas operações. Por exemplo, vejamos a implementação de um método de percurso in-order.

public class ExibirInOrderVisitor implements ArvoreVisitor {

	@Override
	public void visitar(No no) {
		if (no == null)
			return;
		this.visitar(no.getEsquerdo());
		System.out.println(no);
		this.visitar(no.getDireito());
	}

}

Seguindo a ideia de implementação de percurso in-order [2], primeiro é feita a visita ao nó esquerdo, em seguida mostramos no terminal o nó e ao fim é feita a visita ao nó direito. Com esta simples implementação temos o método de percurso in-order da árvore, sem precisar alterar a sua estrutura.

Implementar várias outras operações fica muito simples ao utilizar este padrão. As implementações dos outros métodos de percurso ficam triviais. Uma implementação mais complexo, também fica mais simplificada. Por exemplo, caso seja necessário implementar um método que exibe os nós de uma maneira indentada, de acordo com seu nível na árvore.

public class ExibirIndentadoVisitor implements ArvoreVisitor {

	@Override
	public void visitar(No no) {
		if (no == null) {
			return;
		}
		System.out.println(no);
		visitar(no.getEsquerdo(), 1);
		visitar(no.getDireito(), 1);
	}

	private void visitar(No no, int qtdEspacos) {
		if (no == null) {
			return;
		}
		for (int i = 0; i < qtdEspacos; i++) {
			System.out.print("-");
		}
		System.out.println(no);
		visitar(no.getEsquerdo(), qtdEspacos + 1);
		visitar(no.getDireito(), qtdEspacos + 1);
	}

}

Este método conta a quantidade de espaços para indentação a partir de cada nível de recursão do método. A única restrição das classes visitantes é que implementem o método para visitar. Quaisquer outras operações que precisem de suporte podem ser implementadas.

Um exemplo de cliente seria:

	public static void main(String[] args) {
		ArvoreBinaria arvore = new ArvoreBinaria(7);

		arvore.inserir(15);
		arvore.inserir(10);
		arvore.inserir(5);
		arvore.inserir(2);
		arvore.inserir(1);
		arvore.inserir(20);

		System.out.println("### Exibindo em ordem ###");
		arvore.aceitarVisitante(new ExibirInOrderVisitor());
		System.out.println("### Exibindo pre ordem ###");
		arvore.aceitarVisitante(new ExibirPreOrdemVisitor());
		System.out.println("### Exibindo pós ordem ###");
		arvore.aceitarVisitante(new ExibirPostOrderVisitor());
		System.out.println("### Exibindo identado ###");
		arvore.aceitarVisitante(new ExibirIndentadoVisitor());
	}

O diagrama UML que representa esta solução é o seguinte:

Um pouco de teoria

Como foi exemplificado, o padrão Visitor oferece uma excelente alternativa quando é necessário realizar uma série de operações sobre um conjunto de dados, dado que estas operações são pouco estáveis, ou seja, sofrem alterações constantemente. Um outro exemplo que evidencia mais a aplicabilidade do padrão é na construção de compiladores, como mostrado em [1], onde existem vários tipos de nós da árvore de sintaxe abstrata, e o conjunto de operações é indefinido.

Assim, para decidir pela utilização do padrão Visitor é necessário ter certeza de que a estrutura dos elementos seja bem estável (não sofra alterações ao longo do projeto) e que a interface desta estrutura permita acesso suficiente para os objetos visitantes. Elementos podem ter interfaces diferentes, contato que estas interface sejam estáveis e provejam acesso às classes visitantes.

Outro detalhes importante é que a estrutura de dados depende da interface das classes visitantes. Já a classe visitante precisa ter conhecimento sobre os vários tipo de elementos, pois cada um deles poderá ser visitado de uma maneira diferente. Para exemplificar esta afirmação, suponha o seguinte cenário:

São utilizadas várias estruturas de dados, como vetores, listas, árvores binárias, árvores B, heaps, etc. Todas estas classes oferecem uma interface simples: adicionar, remover e buscar elementos. Já um método visitante atuaria de maneiras diferentes em cada uma delas. O método de percurso de uma árvore binária é diferente do método de percurso de uma lista, ou de uma árvore B. Assim, na classe visitante, é preciso ter um método para visitar cada um destes tipos de estruturas, embora todas elas tenham uma interface em comum.

Se por um lado o padrão facilita a adição de novas operações sobre o conjunto de estruturas, fica muito difícil, uma vez que o projeto está utilizando o padrão, incluir novos tipos de elementos, pois cada novo elemento vai gerar alterações em todas as classes visitantes.

Padrões que utilizem estruturas de dados para representação podem utilizar o padrão Visitor, por exemplo, uma estrutura Composite ou Interpreter, pode oferecer um método de visita e atribuir para as classes visitantes a responsabilidade das operações sobre seu conjunto de dados.

Já que o padrão Visitor é utilizado para percorrer um conjunto de dados, qual a diferença dele e do padrão Iterator? A intenção do padrão Iterator é fornecer uma maneira de percorrer os elementos de uma estrutura, expondo seus elementos e deixando para o cliente a responsabilidade de operar sobre estes. O padrão Visitor oferece operações sobre elementos, sem expor seu conteúdo, ou delegar responsabilidades extras para o cliente.

Código fonte completo

O código completo pode ser baixado no seguinte repositório Git: https://github.com/MarcosX/Padr-es-de-Projeto.

Os arquivos estão como um projeto do eclipse, então basta colocar no seu Workspace e fazer o import.

Se gostou do post compartilhe com seus amigos e colegas, senão, comente o que pode ser melhorado. Encontrou algum erro no código? Comente também. Possui alguma outra opinião ou alguma informação adicional? Comenta ai! 😀

Referências:

[1] GAMMA, Erich et al. Padrões de Projeto: Soluções reutilizáveis de software orientado a objetos.
[2] WIKIPEDIA. Tree Traversal: http://en.wikipedia.org/wiki/Tree_traversal. Acesso em 24 de novembro de 2011.