Em DEITEL (2005, pág. 673), uma coleção é uma estrutura de dados, na realidade um objeto, que pode armazenar ou agrupar referências a outros objetos (um contêiner). As classes e interfaces da estrutura de coleções são membros do pacote java.util e a Figura 1 apresenta a hierarquia de algumas dessas classes e interfaces oferecidas pelo Java.
Figura 1: Hierarquia das interfaces da estrutura de coleções. Disponível na Internet via WWW. URL: http://www.falkhausen.de/en/diagram/html/java.util.Collection.html. Novembro, 2012.
Na lista de interfaces da estrutura de coleções destacam-se: 1) conjuntos; 2) listas; 3) filas; e, 4) mapas.
1) Conjunto (Set e SortedSet):
Uma coleção de elementos que modela a abstração matemática para conjuntos. Cada elemento pertence ou não pertence ao conjunto (não há elementos repetidos). Podem ser mantidos ordenados (SortedSet) ou não.
2) Lista (List):
Uma coleção indexada de objetos às vezes chamada de sequência. Como nos vetores, índices de List são baseados em zero, isto é, o índice do primeiro elemento é zero. Além dos métodos herdados de Collection, List fornece métodos para manipular elementos baseado na sua posição (ou índice) numérica na lista, remover determinado elemento, procurar as ocorrências de um dado elemento e percorrer sequencialmente (ListIterator) todos os elementos da lista. A interface List é implementada por várias classes, incluídas as classes ArrayList (implementada como vetor), LinkedList e Vector.
3) Fila (Queue):
Uma coleção utilizada para manter uma "fila" de elementos. Existe uma ordem linear para as filas que é a "ordem de chegada". As filas devem ser utilizadas quando os itens deverão ser processados de acordo com a ordem "PRIMEIRO-QUE-CHEGA, PRIMEIRO-ATENDIDO". Por esta razão as filas são chamadas de Listas FIFO, termo formado a partir de "First-In, First-Out".
4) Mapa (Map e SortedMap):
Um mapa armazena pares, chave e valor, chamados de itens. As chaves não podem ser duplicadas e são utilizadas para localizar um dado elemento associado. As chaves podem ser mantidas ordenadas (SortedMap) ou não.
Conjuntos (Set)
Um Set é uma Collection que contém elementos únicos (não duplicados). A estrutura de coleções contém diversas implementações de Set, incluindo HashSet e TreeSet:
- HashSet: armazena seus elementos em uma tabela de hash. A ideia central do hash é utilizar uma função, aplicada sobre parte da informação (chave), para retornar o índice onde a informação deve ou deveria estar armazenada.
- TreeSet: armazena seus elementos em uma árvore. Uma árvore é uma estrutura de dados que se caracteriza por uma relação de hierarquia entre os elementos que a compõem. TreeSet utiliza-se de uma árvore binária para alinhar os elementos. Segundo Knuth apud Ziviani (2005) uma árvore binária é definida como um conjunto finito de nós que ou está vazio ou consiste de um nó chamado de raiz mais os elementos de duas árvores binárias distintas chamadas de subárvore esquerda e subárvore direita do nó raiz. Uma árvore binária de pesquisa é uma árvore binária em que todo nó não-terminal contém um registro, e, para cada nó, a seguinte propriedade é verdadeira: todos os registros com chaves menores estão na subárvore esquerda e todos os registros com chaves maiores estão na subárvore direita.
Conjuntos classificados (SortedSet)
A estrutura de coleções disponibiliza a interface SortedSet (que estende Set) para conjuntos que mantêm seus elementos na ordem de classificação, a ordem natural dos elementos (por exemplo, um conjunto de números estão em ordem crescente) ou em uma ordem especificada por um Comparator. A classe TreeSet implementa SortedSet.
Para atender o propósito deste artigo será utilizada a classe TreeSet na criação de jogos com 6 (seis) dezenas para serem utilizados em apostas da Mega-Sena. Veja a seguir a relação dos principais métodos da classe. Disponível na Internet via WWW. URL: http://docs.oracle.com/javase/1.4.2/docs/api/java/util/TreeSet.html. Novembro, 2012.
- boolean add(Object o): adiciona o elemento especificado no conjunto se ele ainda "não" estiver presente.
- boolean addAll(Collection c): adiciona todos os elementos do conjunto especificado.
- void clear(): remove todos os elementos do conjunto.
- boolean contains(Object o): retorna verdadeiro se o elemento especificado pertence/está contido no conjunto.
- Object first(): retorna o primeiro elemento do conjunto classificado.
- Iterator iterator(): retorna um iterador sobre os elementos do conjunto.
- Object last(): retorna o ultimo elemento do conjunto classificado.
- boolean remove(Object o): remove o elemento especificado do conjunto se ele estiver presente.
- int size(): retorna o número de elementos do conjunto (sua cardinalidade).
- SortedSet subSet(Object o1, Object o2): retorna um subconjunto formado pelos elementos do conjunto compreendidos do elemento "o1", até o elemento "o2". Incluindo "o1" e excluindo "o2" no resultado.
A Listagem 1 apresenta uma classe Java que demonstra a utilização da classe TreeSet para manter dois conjuntos de números inteiros classificados, "jogo" e "usados". No conjunto "jogo", a cada passo da primeira instrução de repetição for (variável de controle "i"), será gerada uma aposta com 6 dezenas. Já no conjunto "usados" serão armazenas todas as dezenas já utilizadas em apostas anteriores. Na execução da segunda instrução de repetição "for" (variável de controle "j") será criado o i-ésimo jogo, gerando e aceitando somente números no intervalo entre 1 e 60 (inclusive) que ainda não foram usados nas apostas anteriores: do – while (usados.contains(n)). Para mostrar as dezenas do i-ésimo jogo foi implementada uma estrutura de repetição "for" aprimorada usando o iterator "item".
Listagem 1: Criando jogos para Mega-Sena
import java.util.SortedSet;
import java.util.TreeSet;
public class Exemplo {
public static void main(String[] args) {
SortedSet<Integer> jogo = new TreeSet<Integer>();
SortedSet<Integer> usados = new TreeSet<Integer>();
int i, j, n;
System.out.printf("+------------------------------+\n");
System.out.printf("| M E G A - S E N A |\n");
System.out.printf("+------------------------------+\n");
for (i=1; i<=10; i++) {
// cria uma aposta com 6 dezenas
jogo.clear();
for (j=1; j<=6; j++) {
// aceita somente números que ainda não foram usados
do {
// gera um número aleatório entre 1 e 60 (inclusive)
n = (int)Math.round(Math.random() * 59) + 1;
} while (usados.contains(n));
jogo.add(n);
usados.add(n);
}
// mostra os elementos do i-ésimo jogo usando iterator (item)
// e uma estrutura de repetição "for" aprimorada
System.out.printf("| %2do. Jogo: ", i);
for (Integer item: jogo) {
System.out.printf("%2d ", item);
}
System.out.printf("|\n");
System.out.printf("+------------------------------+\n");
}
}
}Como resultado da execução da classe "Exemplo", apresentado na Figura 2, serão fornecidos 10 jogos com 6 dezenas sem repetição de números (10 x 6, representam os 60 números possíveis da mega-sena).
Figura 2: Executando a classe "Exemplo" na criação de jogos para apostas na Mega-Sena
Referências bibliográficas
- DEITEL, H. M. (2005) Java: Como Programar. São Paulo: Person Prentice Hall, 6ª edição. Capítulo 19: Coleções, páginas 673-714.
- ZIVIANI, Nivio. (2005) Progeto de Algoritmos com implementação em PASCAL e C. São Paulo: Ed. Thompson.
Obrigado e um abraço.
