UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO
Projeto de Sistemas III
Professor Júlio
Alunos:
Danielle Costa Lopes Gonçalves da Silva.
Maurício dos Reis Brum.
Anderson Pereira Bastos.
Paulo Roberto Moura de Carvalho.
Trabalho sobre o padrão Strategy
Intenção
Definir uma família de algoritmos de ordenação de um arranjo, encapsular cada um deles e
torna-los intercambiáveis. Strategy permite que o algoritmo varie independentemente dos clientes
que o utilizam.
Sinônimo
Policy.
Motivação
Existem muitos algoritmos para ordenar uma lista. Implementar no corpo dos clientes cada um
deles é contraproducente:
•
•
•
Os clientes se tornariam muito grandes se embutissem em si mesmos a implementação de
cada um deles.
Algoritmos de ordenação são ótimos com certos arranjos quando comparado com os demais,
assim, seria interessante manter uma biblioteca com os diferentes algoritmos à disposição
dos clientes.
Adicionar novos algoritmos ou fazer manutenção nos existentes requereria um esforço extra
para localizar onde estão implementados cada algoritmo.
Estes problemas podem ser evitados se forem definidas classes que encapsulam os diferentes
algoritmos de ordenação.
Ordenação é o responsável pela ordenação de uma lista, que pode ser pelo nome do aluno ou
pela nota. As estratégias de ordenação não são implementadas por Ordenação, mas sim pelas
subclasses da interface Sort. As subclasses de Sort implementam diferentes estratégias:
•
•
•
•
BubbleSort: Estratégia de fácil manutenção e de baixo consumo de memória, indicado para
arranjos pequenos.
SelectionSort: Estratégia de fácil manutenção, cerca de 40% mais eficiente que
BubbleSort, porém consome muito mais memória. Também indicado para arranjos
pequenos.
InsertionSort: Muito eficiente para arranjos quase ordenados, por exemplo uma tabela já
ordenada que recebe um novo registro ou tem um registro modificado.
Cada uma das estratégias acima tem duas subclasses: uma para ordenar pelo nome e outra
pela nota. O fato de ambos os tipos de dados serem de natureza diferente requer que seja
criada uma estratégia para cada caso pois a forma com que se compara strings difere de
quando se compara números de ponto flutuante. Pelo menos, em Java, os operadores de
comparação atuam em nível de ponteiro para strings. “nome” == “nome” quase sempre
retorna falso em Java.
Uma Ordenação mantém uma referência para um objeto da classe Sort. Sempre que um Cliente
solicita a ordenação do seu vetor a ela, Ordenação repassa a tarefa para o seu objeto ordenador
(classe Sort). O Cliente especifica a estratégia quando constrói o objeto Ordenação, assim, o
Cliente tem a liberdade de ter qualquer número de ordenadores, cada qual com uma estratégia
diferente.
Aplicabilidade
Vide página 293>.
Estrutura
Vide página 294>.
Participantes
•
•
•
•
Strategy (Sort)
ConcreteStrategy(BubbleSortPorNome,
BubbleSortPorNota,
SelectionSortPorNome,
SelectionSortPorNota, InsertionSortPorNome, InsertionSortPorNota)
Context (Ordenacao)
A classe Janela faz o papel de Cliente.
Colaborações
Vide página 294>.
Conseqüências
Vide página 294>.
Implementação
1. Definindo as interfaces de Sort e Ordenação. Ordenação chama o método ordenar() do
seu objeto Sort (ordenador), passando como parâmetro uma referência à lista a ser ordenada.
2. Cliente. O cliente passa uma referência à lista a ser ordenada quando constrói o seu objeto
Ordenacao.
Exemplos de código
O Cliente instancia um objeto Ordenação, passando como parâmetros a lista e um objeto de uma
subclasse de Sort. A seguir tudo que o cliente tem a fazer é chamar a operação getListaOrdenada()
de Ordenação toda vez que necessitar de obter uma cópia ordenada de sua lista.
//======================================Janela.java========================================
//====Foram omitidos trechos de código irrelevantes para a compreensão do padrão.
/*
* Janela.java
*
* Created on 24 de Agosto de 2005, 13:45
*/
public class Janela extends javax.swing.JFrame {
private Lista lista;
(…)
private void btnOrdenarComInsertionSortActionPerformed(java.awt.event.ActionEvent evt) {//GENFIRST:event_btnOrdenarComInsertionSortActionPerformed
//defino qual ordenacao vou usar
estrategia.Sort is;
if(this.radioPorNome.isSelected())
is = new estrategia.InsertionSortPorNome();
else
is = new estrategia.InsertionSortPorNota();
//construo a Ordenacao passando a lista e o ordenador escolhido
try{
estrategia.Ordenacao ordenacao = new estrategia.Ordenacao((Lista)this.lista.clone(),
is);
Lista lista_ordenada = ordenacao.getListaOrdenada();
(...)
}//GEN-LAST:event_btnOrdenarComInsertionSortActionPerformed
private void btnOrdenarComSelectionSortActionPerformed(java.awt.event.ActionEvent evt) {//GENFIRST:event_btnOrdenarComSelectionSortActionPerformed
//defino qual ordenacao vou usar
estrategia.Sort ss;
if(this.radioPorNome.isSelected())
ss = new estrategia.SelectionSortPorNome();
else
ss = new estrategia.InsertionSortPorNota();
//construo a Ordenacao passando a lista e o ordenador escolhido
try{
estrategia.Ordenacao ordenacao = new estrategia.Ordenacao((Lista)this.lista.clone(),
ss);
Lista lista_ordenada = ordenacao.getListaOrdenada();
(...)
}//GEN-LAST:event_btnOrdenarComSelectionSortActionPerformed
private void btnOrdenarComBubbleSortActionPerformed(java.awt.event.ActionEvent evt) {//GENFIRST:event_btnOrdenarComBubbleSortActionPerformed
//defino qual ordenacao vou usar
estrategia.Sort bbs;
if(this.radioPorNome.isSelected())
bbs = new estrategia.BubbleSortPorNome();
else
bbs = new estrategia.BubbleSortPorNota();
//construo a Ordenacao passando a lista e o ordenador escolhido
try{
estrategia.Ordenacao ordenacao = new estrategia.Ordenacao((Lista)this.lista.clone(),
bbs);
Lista lista_ordenada = ordenacao.getListaOrdenada();
(...)
}//GEN-LAST:event_btnOrdenarComBubbleSortActionPerformed
(...)
private javax.swing.JButton btnOrdenarComBubbleSort;
private javax.swing.JButton btnOrdenarComInsertionSort;
private javax.swing.JButton btnOrdenarComSelectionSort;
(...)
}
Ordenação ao ser instanciado recebe uma referência ao Cliente e a um objeto de uma das subclasses
de Sort. Toda vez que o Cliente requer que uma ordenação seja feita, Ordenação, que tem uma uma
referência à lista do cliente, produz uma cópia da lista (em se desejando manter a lista original) e a
repassa como parâmetro para o objeto ordenador (Sort), chamando sua operação ordenar().
//======================================Ordenacao.java========================================
package estrategia;
import java.util.Vector;
public class Ordenacao {
private programa.Lista ref_lista; //o cliente vai passar uma referência à lista
private Sort ordenador;
public Ordenacao(programa.Lista plista, Sort qual_sort) {
//o cliente constrói a Ordencao passando por parâmetros
//uma referência ao objeto lista
//uma referência a uma subclasse concreta de Sort
//que vai determinar qual o algoritmo de ordenação a ser usado
//e por qual campo (se é por nome ou por nota)
ref_lista = plista;
ordenador = qual_sort;
}
public programa.Lista getListaOrdenada() {
//obtem uma copia da lista, pois quero preservar a original
//programa.Lista copia_lista = new programa.Lista();
//copia_lista.setLista((Vector)ref_lista.getLista().clone());
ordenador.ordenar(ref_lista);
//((programa.EntradaLista)copia_lista.getLista().get(0)).setStrNome("zzzzz");
return ref_lista;
}
}
A interface Sort. A operação ordenar() coloca em ordem crescente os elementos da lista cuja
referência é passada como parâmetro.
//======================================Sort.java========================================
package estrategia;
public abstract class Sort {
public abstract void ordenar(programa.Lista lista);
}
As subclasses de Sort(). Elas implementam a operação ordenar(), implementando-a de acordo com
a estratégia a que elas se propõem. A rigor todas as sublcasses de Sort fazem a mesma coisa. A
diferença reside apenas nas diferenças de desempenho, consumo de memória, facilidade de
manutenção nas diversas circunstâncias e por qual informação se deseja ordenar a lista.
//======================================BubbleSort.java========================================
package estrategia;
public abstract class BubbleSort extends Sort {
public abstract void ordenar(programa.Lista lista);
}
//======================================BubbleSortPorNome.java=================================
package estrategia;
public class BubbleSortPorNome extends BubbleSort{
public void ordenar(programa.Lista lista) {
//algoritmo original, com vetor de char
//
for (int i = vetor.length; --i >= 0; )
//
for (int j = 0; j < i; j++)
//
if (vetor[j] > vetor[j+1]) {
//
char temp = vetor[j];
//
vetor[j] = vetor[j + 1];
//
vetor[j + 1] = temp;
//
}
for (int i = lista.getLista().size(); --i >= 0; )
for (int j = 0; j < i; j++){
programa.EntradaLista el1 = (programa.EntradaLista)(lista.getLista().get(j));
programa.EntradaLista el2 = (programa.EntradaLista)(lista.getLista().get(j+1));
if(el1.getStrNome().compareToIgnoreCase(el2.getStrNome()) > 0) {
String tempNome = el1.getStrNome();
float tempNota = el1.getFltNota();
el1.setStrNome(el2.getStrNome());
el1.setFltNota(el2.getFltNota());
el2.setStrNome(tempNome);
el2.setFltNota(tempNota);
}
}
}
public BubbleSortPorNome() {
}
}
//======================================BubbleSortPorNota.java=================================
package estrategia;
public class BubbleSortPorNota extends BubbleSort{
public void ordenar(programa.Lista lista) {
//algoritmo original, com vetor de char
//
for (int i = vetor.length; --i >= 0; )
//
for (int j = 0; j < i; j++)
//
if (vetor[j] > vetor[j+1]) {
//
char temp = vetor[j];
//
vetor[j] = vetor[j + 1];
//
vetor[j + 1] = temp;
//
}
for (int i = lista.getLista().size(); --i >= 0; )
for (int j = 0; j < i; j++){
programa.EntradaLista el1 = (programa.EntradaLista)(lista.getLista().get(j));
programa.EntradaLista el2 = (programa.EntradaLista)(lista.getLista().get(j+1));
if(el1.getFltNota() > el2.getFltNota()) {
String tempNome = el1.getStrNome();
float tempNota = el1.getFltNota();
el1.setStrNome(el2.getStrNome());
el1.setFltNota(el2.getFltNota());
el2.setStrNome(tempNome);
el2.setFltNota(tempNota);
}
}
}
public BubbleSortPorNota() {
}
}
//======================================InsertionSort.java========================================
package estrategia;
public abstract class InsertionSort extends Sort {
public abstract void ordenar(programa.Lista lista);
}
//======================================InsertionSortPorNome.java=================================
package estrategia;
public class InsertionSortPorNome extends InsertionSort{
public InsertionSortPorNome() {
}
public void ordenar(programa.Lista lista) {
//algoritmo original, com vetor de char
//
for (int i = 1; i < vetor.length; i++) {
//
int j = i;
//
char B = vetor[i];
//
while ((j > 0) && (vetor[j-1] > B)) {
//
vetor[j] = vetor[j-1];
//
j--;
//
}
//
vetor[j] = B;
//
}
for (int i = 1; i < lista.getLista().size(); i++) {
int j = i;
programa.EntradaLista B = new programa.EntradaLista("", 0f);
B.setStrNome(((programa.EntradaLista)lista.getLista().get(i)).getStrNome());
B.setFltNota(((programa.EntradaLista)lista.getLista().get(i)).getFltNota());
while ((j > 0) && (((programa.EntradaLista)lista.getLista().get(j1)).getStrNome().compareToIgnoreCase(B.getStrNome()) > 0)) {
programa.EntradaLista el1 = (programa.EntradaLista)lista.getLista().get(j-1);
programa.EntradaLista el2 = (programa.EntradaLista)lista.getLista().get(j);
el2.setStrNome(el1.getStrNome());
el2.setFltNota(el1.getFltNota());
j--;
}
((programa.EntradaLista)lista.getLista().get(j)).setStrNome(B.getStrNome());
((programa.EntradaLista)lista.getLista().get(j)).setFltNota(B.getFltNota());
}
}
}
//======================================InsertionSortPorNota.java=================================
package estrategia;
public class InsertionSortPorNota extends InsertionSort{
public InsertionSortPorNota() {
}
public void ordenar(programa.Lista lista) {
//algoritmo original, com vetor de char
//
for (int i = 1; i < vetor.length; i++) {
//
int j = i;
//
char B = vetor[i];
//
while ((j > 0) && (vetor[j-1] > B)) {
//
vetor[j] = vetor[j-1];
//
j--;
//
}
//
vetor[j] = B;
//
}
for (int i = 1; i < lista.getLista().size(); i++) {
int j = i;
programa.EntradaLista B = new programa.EntradaLista("", 0f);
B.setStrNome(((programa.EntradaLista)lista.getLista().get(i)).getStrNome());
B.setFltNota(((programa.EntradaLista)lista.getLista().get(i)).getFltNota());
while ((j > 0) && (((programa.EntradaLista)lista.getLista().get(j-1)).getFltNota() >
B.getFltNota())) {
programa.EntradaLista el1 = (programa.EntradaLista)lista.getLista().get(j-1);
programa.EntradaLista el2 = (programa.EntradaLista)lista.getLista().get(j);
el2.setStrNome(el1.getStrNome());
el2.setFltNota(el1.getFltNota());
j--;
}
((programa.EntradaLista)lista.getLista().get(j)).setStrNome(B.getStrNome());
((programa.EntradaLista)lista.getLista().get(j)).setFltNota(B.getFltNota());
}
}
}
//======================================SelectionSort.java========================================
package estrategia;
public abstract class SelectionSort extends Sort {
public abstract void ordenar(programa.Lista lista);
}
//======================================SelectionSortPorNome.java=================================
package estrategia;
public class SelectionSortPorNome extends SelectionSort{
public void ordenar(programa.Lista lista) {
//algoritmo original usando vetor de char
// varre o vetor, procurando pelo próximo valor máximo
// e trocando-o com o primeiro elemento da parte não ordenada do vetor
//
for (int i = 0; i < vetor.length - 1; i++ )
//
{
//
int minIndice = i;
// indice do menor valor
//
char min = vetor[minIndice];
// o menor valor
//
// encontrar o menor valor da parte não ordenada do vetor.
//
for ( int j = i + 1; j < vetor.length; j++ )
//
{
//
// If this element is less than min it becomes the min.
//
// se o elemento atual é menor do que o mínimo, ele se torna o mínimo
//
if ( vetor[j] < min )
//
{
//
minIndice = j;
//
min = vetor[minIndice];
//
}
//
}
//
//troca o 1o elemento na parte não ordenada
//
// com o item de menor valor (mesmo que o 1o item já seja o menor)
//
char T = vetor[minIndice];
//
vetor[minIndice] = vetor[i];
//
vetor[i] = T;
//
}
for (int i = 0; i < lista.getLista().size() - 1; i++ )
{
int minIndice = i;
// indice do menor valor
//o menor valor
String strMinNome =
((programa.EntradaLista)lista.getLista().get(minIndice)).getStrNome();
// encontrar o menor valor da parte não ordenada da lista.
for ( int j = i + 1; j < lista.getLista().size(); j++ )
{
// se o elemento atual é menor do que o mínimo, ele se torna o mínimo
if (
((programa.EntradaLista)lista.getLista().get(j)).getStrNome().compareToIgnoreCase(strMinNome) < 0 )
{
minIndice = j;
strMinNome =
((programa.EntradaLista)lista.getLista().get(minIndice)).getStrNome();
}
}
//troca o 1o elemento na parte não ordenada
// com o item de menor valor (mesmo que o 1o item já seja o menor)
String strTmpNome =
((programa.EntradaLista)lista.getLista().get(minIndice)).getStrNome();
float fltTmpNota =
((programa.EntradaLista)lista.getLista().get(minIndice)).getFltNota();
((programa.EntradaLista)lista.getLista().get(minIndice)).setStrNome(((programa.EntradaLista)lista.ge
tLista().get(i)).getStrNome());
((programa.EntradaLista)lista.getLista().get(minIndice)).setFltNota(((programa.EntradaLista)lista.ge
tLista().get(i)).getFltNota());
((programa.EntradaLista)lista.getLista().get(i)).setStrNome(strTmpNome);
((programa.EntradaLista)lista.getLista().get(i)).setFltNota(fltTmpNota);
}
}
public SelectionSortPorNome() {
}
}
//======================================SelectionSortPorNota.java=================================
package estrategia;
public class SelectionSortPorNota extends SelectionSort{
public void ordenar(programa.Lista lista) {
//algoritmo original usando vetor de char
// varre o vetor, procurando pelo próximo valor máximo
// e trocando-o com o primeiro elemento da parte não ordenada do vetor
//
for (int i = 0; i < vetor.length - 1; i++ )
//
{
//
int minIndice = i;
// indice do menor valor
//
char min = vetor[minIndice];
// o menor valor
//
// encontrar o menor valor da parte não ordenada do vetor.
//
for ( int j = i + 1; j < vetor.length; j++ )
//
{
//
// If this element is less than min it becomes the min.
//
// se o elemento atual é menor do que o mínimo, ele se torna o mínimo
//
if ( vetor[j] < min )
//
{
//
minIndice = j;
//
min = vetor[minIndice];
//
}
//
}
//
//troca o 1o elemento na parte não ordenada
//
// com o item de menor valor (mesmo que o 1o item já seja o menor)
//
char T = vetor[minIndice];
//
vetor[minIndice] = vetor[i];
//
vetor[i] = T;
//
}
for (int i = 0; i < lista.getLista().size() - 1; i++ )
{
int minIndice = i;
// indice do menor valor
//o menor valor
float fltMinNota =
((programa.EntradaLista)lista.getLista().get(minIndice)).getFltNota();
// encontrar o menor valor da parte não ordenada da lista.
for ( int j = i + 1; j < lista.getLista().size(); j++ )
{
// se o elemento atual é menor do que o mínimo, ele se torna o mínimo
if ( ((programa.EntradaLista)lista.getLista().get(j)).getFltNota() < fltMinNota)
{
minIndice = j;
fltMinNota =
((programa.EntradaLista)lista.getLista().get(minIndice)).getFltNota();
}
}
//troca o 1o elemento na parte não ordenada
// com o item de menor valor (mesmo que o 1o item já seja o menor)
String strTmpNome =
((programa.EntradaLista)lista.getLista().get(minIndice)).getStrNome();
float fltTmpNota =
((programa.EntradaLista)lista.getLista().get(minIndice)).getFltNota();
((programa.EntradaLista)lista.getLista().get(minIndice)).setStrNome(((programa.EntradaLista)lista.ge
tLista().get(i)).getStrNome());
((programa.EntradaLista)lista.getLista().get(minIndice)).setFltNota(((programa.EntradaLista)lista.ge
tLista().get(i)).getFltNota());
((programa.EntradaLista)lista.getLista().get(i)).setStrNome(strTmpNome);
((programa.EntradaLista)lista.getLista().get(i)).setFltNota(fltTmpNota);
}
}
public SelectionSortPorNota() {
}
}
Usos conhecidos
Vide página 299>.
Padrão relacionado
Vide página 300>.
>
Gamma, E; Helm, R.; Johnson, R; Vlissides, J.
objetos. Ed. Bookman. Porto Alegre, 2005.
>
Gamma, E; Helm, R.; Johnson, R; Vlissides, J.
objetos. Ed. Bookman. Porto Alegre, 2005.
>
Gamma, E; Helm, R.; Johnson, R; Vlissides, J.
objetos. Ed. Bookman. Porto Alegre, 2005.
>
Gamma, E; Helm, R.; Johnson, R; Vlissides, J.
objetos. Ed. Bookman. Porto Alegre, 2005.
>
Gamma, E; Helm, R.; Johnson, R; Vlissides, J.
objetos. Ed. Bookman. Porto Alegre, 2005.
>
Gamma, E; Helm, R.; Johnson, R; Vlissides, J.
objetos. Ed. Bookman. Porto Alegre, 2005.
Padrões de Projeto – Soluções reutilizáveis de software orientado a
Padrões de Projeto – Soluções reutilizáveis de software orientado a
Padrões de Projeto – Soluções reutilizáveis de software orientado a
Padrões de Projeto – Soluções reutilizáveis de software orientado a
Padrões de Projeto – Soluções reutilizáveis de software orientado a
Padrões de Projeto – Soluções reutilizáveis de software orientado a