Colecoes

Aula 16: Estudo de Caso: A API de Coleções do Java Você não pode ser um programador Java competente sem compreender as partes cruciais da biblioteca Java. Os tipos básicos estão todos em java.lang, e são parte da linguagem propriamente dita. O package java.util fornece coleções - conjuntos, lista e mapas - e você deve conhecer este pacote muito bem. O package java.io também é importante, mas você pode se virar mesmo sem ter muita familiaridade com este pacote, pesquisando-o melhor quando necessário. Nesta aula, analisaremos o projeto do pacote java.util, muitas vezes chamado de 'API de coleções'. É importante compreender não apenas o porquê das coleções serem extremamente úteis, mas também o porquê a API de coleções ser um ótimo exemplo de código bem projetado. A API é de muito fácil compreensão, estando muito bem documentada. Ela foi projetada e escrita por Joshua Bloch, que escreveu o livro Effective Java que recomendamos no início do curso. Ao mesmo tempo, quase todas as complexidades da programação orientada a objetos aparecem em algum lugar na API, portanto, se você estudá-la cuidadosamente, obterá uma ampla compreensão dos tópicos de programação que você, provavelmente, ainda não utilizou no seu código. De fato, não seria um exagero dizer que se você compreender inteiramente apenas uma das classes, ArrayList por exemplo, então você terá se tornado um mestre em todos os conceitos do Java. Não teremos tempo de olhar todos os tópicos hoje, mas iremos abordar muitos deles. Alguns deles, como serialização, estão além do escopo do curso.

16.1 Hierarquia de Tipos Aproximadamente, a API oferece três tipos de coleções: conjuntos, listas e mapas. O conjunto é uma coleção de elementos que não mantém uma ordem nem uma contagem dos elementos - cada elemento ou está no conjunto ou não. Uma lista é uma seqüência de elementos e, portanto, mantém dados a respeito de ambos, a ordem e a contagem. Um mapa é uma associação entre chaves e valores: ele mantém um conjunto de chaves e mapeia cada chave para um único valor. A API organiza suas classes em uma hierarquia de interfaces - as especificações dos vários tipos - e em uma hierarquia de implementação de classes em separado. O diagrama abaixo demonstra algumas classes de interfaces selecionadas para ilustrar a organização hierárquica. A interface Collection captura as propriedades comuns das listas e dos conjuntos, mas não dos mapas, mas iremos utilizar o termo informal 'coleções' para, também, nos referirmos aos mapas. SortedMap e SortedSet são interfaces utilizadas pelos mapas e por conjuntos que fornecem operações adicionais para recuperar os elementos em alguma ordem.

As implementações concretas de classes, como LinkedList, estão construídas no topo do esqueleto das implementações, assim como AbstractList da qual LinkedList descende. Esta estrutura paralela de interfaces e classes é uma importante forma de estruturação de código, ou seja, um idioma importante para ser estudado. Muitos programadores inexperientes são tentados a utilizar classes abstratas quando deveriam estar utilizando interfaces. Mas em geral, você deve preferir as interfaces ao invés das classes abstratas. Não é fácil de se aperfeiçoar uma classe existente fazendo com que ela estenda uma classe abstrata (pois uma classe só pode ter no máximo uma super classe), mas normalmente é fácil fazer com que a classe implemente uma nova interface. Bloch mostra (no capítulo 16 de seu livro: 'Prefira Interfaces ao Invés de Classes Abstratas') como combinar as vantagens de ambas, utilizando uma implementação de classes organizada na forma de um esqueleto de hierarquias, como ele faz aqui na API de coleções. Você terá as vantagens das interfaces para alcançar o desacoplamento baseado em especificações, e as vantagens das classes abstratas para fabricar código compartilhado entre implementações relacionadas.

Cada interface do Java vem com uma especificação informal na documentação da API Java. Este fato é importante, pois a especificação informa ao usuário de uma classe que implementa uma interface, o que esperar da interface. Se você implementar uma classe e quiser que esta classe satisfaça à especificação List, por exemplo, você deve garantir que esta classe satisfaz à especificação informal também, do contrário, ela irá falhar com relação ao comportamento esperado pelos programadores. Estas especificações são, intencionalmente, incompletas (assim como o são muitas especificações). As classes concretas também possuem especificações, e estas especificações preenchem alguns dos detalhes das interfaces. A interface List, por exemplo, não especifica se elementos não nulos podem ser armazenados, mas as classes ArrayList e LinkedList informam explicitamente que elementos nulos são permitidos. A classe HashMap admite tanto valores nulos quanto chaves nulas, diferente de Hashtable, que não permite nenhum dos dois. Quando você escreve código que utiliza classes da API de coleções, deve se referir a um objeto através da interface ou classe mais genérica possível. Por exemplo, List p = new LinkedList (); é um estilo melhor do que LinkedList p = new LinkedList (); se o seu código compilar com a primeira versão do exemplo acima, então você pode facilmente migrar para uma lista diferente em uma implementação posterior: List p = new ArrayList (); pois todo o código subseqüente será baseado apenas no fato de p ser do tipo List. Utilizando-se a segunda versão do exemplo anterior, no entanto, você pode descobrir que não será capaz de fazer a alteração, pois algumas partes do seu programa realizam operações sobre x que apenas a classe LinkedList fornece - uma operação que, de fato, pode não ser necessária. Isto está explicado em mais detalhes no item 34 do livro de Bloch ('Refira-se aos Objetos através de suas Interfaces'). Veremos um exemplo mais sofisticado deste tipo de ocorrência no estudo de caso de uma aula próxima, onde parte do código requer acesso às chaves de HashMap. Ao invés da passarmos todo o mapa passamos apenas uma visão do tipo Set:

Set keys = map.keySet (); agora o código que utiliza as chaves nem mesmo sabe que este conjunto é um conjunto de chaves de um mapa.

16.2 Métodos Opcionais A API de coleções permite que uma classe implemente uma interface de coleções sem que implemente todos os seus métodos. Por exemplo, todos os métodos do tipo modificadores da interface List são especificados como opcionais, ou optional. Isto significa que você pode implementar uma classe que satisfaz à especificação de List, mas que joga uma exceção UnsupportedOperationException toda vez que você chamar um método do tipo modificador (mutator) como, por exemplo, o método add. Esta fraqueza intencional da especificação da interface List é problemática, pois se você estiver escrevendo algum código que recebe uma lista, você não sabe, na ausência de informações adicionais a respeito da lista, se ela suporta o método add. Mas sem esta noção de operações opcionais, você teria que declarar uma interface separada denominada ImmutableList. Estas interfaces iriam se proliferar em grande número. Algumas vezes, desejamos alguns métodos modificadores e outros não. Por exemplo, o método keySet da classe HashMap retorna um conjunto (um objeto Set) contendo as chaves do mapa. O conjunto é uma visão: deletar uma chave do conjunto faz com que uma chave e seu valor associado sejam deletados do mapa. Então, o método remove é suportado. Mas o método add não, pois você não pode adicionar uma chave ao mapa sem um valor associado à chave. Portanto, a utilização das operações opcionais é um julgamento de engenharia. Isto significa menos checagens em tempo de compilação, mas reduz o número de interfaces.

16.3 Polimorfismo Todos estes containers - conjuntos, listas e mapas - recebem elementos do tipo Object. Estes containers são considerados polimórficos, o que significa 'muitas formas', pois eles permitem que você construa diferentes tipos de containers: listas de inteiros, listas de URLs, listas de listas, e assim por diante. Este tipo de polimorfismo é denominado polimorfismo de subtipo, pois se baseia na hierarquia de tipos. Uma forma diferente de polimorfismo, denominada polimorfismo paramétrico, permite que você defina containers através de parâmetros que indicam o tipo, de maneira que um cliente possa

indicar que tipo de elemento um container em específico irá conter: List[URL] bookmarks; // ilegal em Java Java não admite este tipo de polimorfismo, no entanto, já existiram muitas propostas para adicionálo. O polimorfismo paramétrico possui a grande vantagem de que o programador pode dizer ao compilador qual o tipo dos elementos. O compilador pode, então, interceptar erros nos quais um tipo errado é inserido, ou quando um elemento que é extraído for tratado como sendo de um tipo diferente. Através do polimorfismo de subtipo, você deve explicitamente moldar os elementos durante a recuperação, através da operação de cast. Considere o código: List bookmarks = new LinkedList (); URL u = …; bookmarks.add (u); … URL x = bookmarks.get (0); // o compilador irá rejeitar esta sentença A sentença que adiciona u está correta, pois o método add aguarda um objeto, e URL é uma subclasse de Object. A sentença que recupera x, no entanto, está errada, pois o tipo retornado pela sentença do lado direito do operador = retorna um Object, e você não pode atribuir um Object para uma variável do tipo URL, pois você não poderia se basear naquela variável como sendo uma URL. Portanto, uma operação de downcast é necessária, e precisamos escrever o seguinte código: URL x = (URL) bookmarks.get (0); O efeito da operação de downcast é realizar uma checagem em tempo de execução. Se a checagem tiver sucesso, e o resultado da chamada do método é do tipo URL, a execução continua normalmente. Caso a checagem falhe, no caso do tipo retornado não ser correto, uma exceção ClassCastException é jogada, e a atribuição não é realizada. Tenha certeza de que você compreende este conceito, e de que não fará nenhuma confusão (como os estudantes geralmente fazem), pensando que a operação de cast, de alguma forma, realiza uma mutação no objeto retornado pelo método. Os objetos carregam seu tipo em tempo de execução, e se um objeto foi criado com um construtor da classe URL, ele terá este tipo sempre, e não há razão para alterá-lo para que venha a ter seu próprio tipo. As operações de downcast podem ser um incômodo e, ocasionalmente, vale a pena escrever uma classe wrapper para automatizar o processo. Em um browser, você provavelmente utilizaria um tipo

abstrato de dados para representar uma lista de bookmarks (que suportasse funções além das oferecidas pelo tipo URL). Fazendo dessa forma, você iria realizar a operação de cast dentro do código do tipo abstrato, e seus clientes veriam códigos como o seguinte: URL getURL (int i); que não iria exigir a operação de cast em seu contexto de invocação, limitando, portanto, o escopo no qual erros de cast poderiam ocorrer. O polimorfismo de subtipo fornece flexibilidades que o polimorfismo paramétrico não fornece. Você pode formar containers heterogêneos que contêm diferentes tipos de elementos. E você pode colocar containers dentro deles próprios - tente descobrir como expressar este fato como um tipo polimórfico - apesar de não ser uma coisa adequada para se fazer. De fato, como mencionamos em nossa aula anterior a respeito de igualdade, a API de classes Java será degenerada se você fizer desta forma. Uma rígida definição do tipo de elemento que um container possui é muitas vezes a parte mais importante de uma invariante rep de um tipo abstrato. Você deve criar o hábito de escrever um comentário toda vez que declarar um container, seja usando uma declaração de tipo pseudoparamétrica: List bookmarks; // List [URL] ou como uma parte da invariante rep propriamente dita: IR: bookmarks.elems in URL

16.4 Implementações Sobre Esqueletos de Hierarquias As implementações concretas das coleções estão construídas sobre esqueletos de hierarquias. Estas implementações utilizam o padrão de projeto denominado Template Method (consulte Gamma et al, páginas 325-330). Uma classe abstrata não possui instâncias de si mesma, mas define métodos denominados templates (moldes) que invocam outros métodos denominados hooks (ganchos) que são declarados como abstratos e que não possuem código. Na subclasse herdeira, os métodos hook são sobrepostos, e os métodos template são herdados sem qualquer alteração. Na classe AbstractList, por exemplo, iterator é um método template que retorna um iterador implementando o método get como um hook. O método equals é implementado como um outro template da mesma forma que o iterator. Uma subclasse, como ArrayList, fornece então uma

representação (uma array de elementos, por exemplo) e uma implementação para o método get (por exemplo, o método deve retornar o i-ésimo elemento do array), podendo herdar os métodos iterator e equals. Algumas classes concretas substituem as implementações abstratas. LinkedList, por exemplo, substitui a funcionalidade do iterador, pois, ao utilizar a representação das entradas como objetos do tipo Entry diretamente, é possível ter-se uma performance melhor do que se utilizando o método get, que é um hook, e realiza uma busca seqüencial em cada invocação!

16.5 Capacidade, Alocação & Garbage Collector Uma implementação que utiliza um array para sua representação - assim como ArrayList e HashMap - deve definir um tamanho para o array quando alocá-lo. A escolha de um tamanho bom pode ser importante para a performance. Pois se o tamanho for muito pequeno, o array terá que ser substituído por um novo array, sendo necessário arcar com os custos de se alocar um novo array e de se liberar a memória do antigo. Se ele for muito grande, teremos perda de espaço, o que será um problema especialmente quando existirem muitas instâncias do tipo da coleção que estamos utilizando. Tais implementações, portanto, fornecem construtores nos quais o cliente pode definir a capacidade inicial, a partir da qual o tamanho da locação pode ser determinado. ArrayList, por exemplo, possui o construtor: public ArrayList(int initialCapacity) Constrói uma lista vazia com a capacidade inicial especificada. Parâmetros: initialCapacity - a capacidade inicial da lista. Throws: IllegalArgumentException - caso a capacidade inicial seja um valor negativo. Existem também métodos que ajustam a alocação: trimToSize, define a capacidade do container de forma que ele seja grande o suficiente para os elementos atualmente armazenados, e ensureCapacity, que garante a capacidade até uma determinada quantia. Utilizar as facilidades para gerenciamento da capacidade pode ser problemático. Se você não sabe exatamente a magnitude das coleções que você irá precisar para sua aplicação, você pode tentar gerar uma estimativa.

Perceba que este conceito de capacidade transforma um problema comportamental em um problema de performance - uma troca desejável. Em muitos programas antigos, existem recursos limitados, e quando eles são exauridos, o programa simplesmente falha. Com a abordagem do gerenciamento de capacidade, o programa simplesmente se torna mais lento. É uma boa idéia projetar um programa de forma que ele funcione eficientemente na maior parte do tempo, mesmo que ocorram problemas de performance ocasionalmente. Se você estudar a implementação do método remove de ArrayList, você verá este código: public Object remove(int index) { … elementData[-size] = null; // deixe que o gc (garbage collector) faça seu trabalho …

O que acontece neste caso? O garbage collector não funciona automaticamente? Neste caso observamos um erro comum de programadores inexperientes. Se você possui um array na sua representação, com uma variável de instância distinta que contém um índice para indicar quais elementos do array devem ser considerados como parte da coleção abstrata. É tentador pensar que, para remover os elementos, tudo que você deve fazer é decrementar este índice. Uma análise sobre a função de abstração do tipo abstrato poderá explicar esta confusão: os elementos que estão acima do índice não são considerados parte da coleção abstrata, e seus valores são irrelevantes. No entanto, há um problema. Se você não garantir a atribuição do valor null para as posições que não são utilizadas, os elementos cujas referências estão nessas posições não serão tratados pelo garbage collector, mesmo que não existam outras referências para estes elementos em qualquer outra parte do programa. O garbage collector não pode interpretar a função abstrata, portanto, ele não sabe que aqueles elementos não podem ser acessados através da coleção, mesmo que seja possível acessá-los através da representação. Se você se esquecer de atribuir null para estas posições, a performance do seu programa pode ser comprometida.

16.6 Cópias, Conversões, Wrappers, etc Todas as classes de coleções concretas fornecem construtores que recebem coleções como argumento. Isto permite que você copie coleções, e que possa converter um tipo de coleção para outro. Por exemplo, a classe, LinkedList possui:

public LinkedList(Collection c) Constrói uma lista contendo os elementos da coleção especificada, na ordem em que eles são retornados pelo iterador da coleção. Parâmetros: c - a coleção cujos elementos devem ser colocados nesta lista. a qual pode ser utilizada para cópia: List p = new LinkedList () … List pCopy = new LinkedList (p) ou para que se crie uma lista encadeada a partir de um outro tipo de coleção: Set s = new HashSet () … List p = new LinkedList (s)

Como não podemos declarar construtores em interfaces, a especificação List não estabelece que todas as suas implementações devem ter tais construtores, apesar de que elas possuem. Existe uma classe especial denominada java.util.Collections que contém um grupo de métodos estáticos que realizam operações sobre coleções ou que retornam coleções como resultado. Alguns destes métodos são algoritmos genéricos (por exemplo, para ordenação), e outros são wrappers. Por exemplo, o método unmodifiableList recebe uma lista e retorna uma lista com os mesmos elementos, mas que é imutável : public static List unmodifiableList(List list) Retorna uma visão não modificável da lista especificada. Este método permite que módulos forneçam aos usuários um acesso "read-only" às suas listas internas. Operações de consulta sobre a lista realizam a consulta na lista original. Tentativas dese modificar a lista retornada, diretamente ou através de um iterador, resultam em uma exceção UnsupportedOperationException. A lista retornada será serializable caso a lista original também o seja. Parâmetros:

list - a lista para a qual uma visão não modificável deve ser retornada. Returns: Uma visão não modificável da lista especificada. A lista retornada não é exatamente imutável, já que seus valores podem ser alterados devido a alterações ocorridas na lista subjacente (veja a seção 16.8 mais abaixo), mas ela não pode ser modificada diretamente. Existem métodos semelhantes que recebem coleções e retornam visões que são sincronizadas com a lista original através de métodos wrappers.

16.7 Coleções Ordenadas Uma coleção ordenada deve possuir alguma forma de se comparar os elementos para se determinar a sua ordem. A API de coleções oferece duas abordagens para fazer isto. Você pode utilizar a 'ordenação natural', que é determinada através do método compareTo do tipo dos elementos armazenados, que devem implementar a interface java.lang.Comparable: public int compareTo(Object o) que retorna um inteiro negativo, zero, ou um inteiro positivo caso o objeto (this) seja menor que, igual, ou maior que um objeto o. Quando você adicionar um elemento em uma coleção ordenada que está utilizando ordenação natural, o elemento deve ser uma instância de uma classe que implementa a interface Comparable. O método add realiza a operação de downcast para o tipo Comparable sobre o elemento adicionado de forma que seja possível compará-lo com os elementos já existentes na coleção, caso não seja possível fazer o downcast, será jogada uma exceção (lembrese que uma operação de downcast é, sobretudo, uma verificação). Alternativamente, você pode utilizar uma ordenação fornecida independentemente dos elementos, através de um elemento que implementa a interface java.util.Comparator, e que possui o método public int compare(Object o1, Object o2) que é semelhante ao método compareTo, mas que recebe como argumento ambos os elementos que serão comparados. Esta é uma instância do padrão denominado Strategy, no qual um algoritmo é desacoplado do código que o utiliza (consulte Gamma, pp. 315-323). Qual abordagem utilizar dependerá de qual construtor você utiliza para criar a coleção de objetos. Se você utilizar o construtor que recebe um Comparator como argumento, ele será utilizado para

determinar a ordenação; se você utilizar o construtor sem argumentos, a ordenação natural será utilizada. A atividade de comparação sofre os mesmos problemas que a igualdade (discutida na aula 9). Uma coleção ordenada possui uma invariante rep que determina que os elementos da representação devem estar ordenados. Se a ordenação de dois elementos puder ser alterada através de uma invocação a um método público, teremos uma exposição de representação.

16.8 Visões Introduzimos o conceito de visões na aula 9. As visões são um mecanismo sofisticado, muito útil, mas perigoso. Elas violam muitas das nossas concepções a respeito de quais tipos de comportamentos podem ocorrer em um programa orientado a objetos bem formado. Três tipos de visões podem ser identificados, de acordo com o propósito da visão: · Extensão de funcionalidade. Algumas visões são utilizadas para estender a funcionalidade de um objeto sem que seja necessária a adição de novos métodos à sua classe. Os iteradores caem nessa categoria. Seria possível, ao invés disso, colocar os métodos next e hasNext na própria classe da coleção. Mas isto iria complicar a API da classe. Seria difícil também suportar múltiplas iterações sobre a mesma coleção. Poderíamos adicionar um método reset à classe que seria invocado para reiniciar uma iteração, mas isto permitiria apenas uma iteração por vez. Tal método poderia conduzir a erros nos quais o programador se esquece de reiniciar a iteração. · Desacoplamento. Algumas visões fornecem um subconjunto das funcionalidades da coleção subjacente. O método keySet da interface Map, por exemplo, retorna um conjunto constituído das chaves do mapa. O método permite, portanto, que a parte do código relacionada com as chaves, mas não a parte relacionada com os valores, seja desacoplada do resto da especificação da interface Map. · Transformação Coordenada. A visão fornecida pelo método subList da interface List provê uma espécie de transformação coordenada. Alterações na visão produzem alterações na lista subjacente. Mas o acesso à lista é realizado através de um índice que é um offset passado através do parâmetro do método subList. As visões são perigosas por duas razões. Primeiro, as coisas são alteradas na camada subjacente: invoque o método remove a partir de um iterador e sua coleção subjacente será alterada; invoque remove em um mapa e uma determinada visão de seu conjunto de chaves será alterada (e viceversa). Esta é uma forma de aliasing abstrato no qual uma alteração em um objeto faz com que outro objeto, de um tipo diferente, seja alterado. Os dois objetos não precisam nem mesmo estar dentro do mesmo escopo léxico. Perceba que o significado de nossa cláusula 'modifies' utilizada em especificações deve ser refinada: se você definir 'modifies c' e c possui uma visão v, isto quer dizer que v também pode ser alterada?

Segundo, a especificação de um método que retorna uma visão muitas vezes limita os tipos de alterações que são permitidas. Para se ter certeza que seu código funciona, você precisará entender a especificação deste método. Sendo que, não surpreendente, estas especificações são muitas vezes obscuras. A cláusula 'post-requires' do texto de Liskov é uma forma de se estender nosso conceito de especificação para se manipular algumas das complicações. Algumas visões permitem que apenas a coleção subjacente seja alterada. Outras permitem que apenas a visão seja alterada - iteradores, por exemplo. Algumas permitem alterações para ambos, a visão e a coleção subjacente, mas determinam complexas implicações em função das alterações. A API de coleções, por exemplo, determina que quando uma visão na forma de uma sublist é criada a partir de uma lista, a lista subjacente não deve sofrer nenhuma modificação estrutural; ou como está explicado na documentação da API: Modificações estruturais são aquelas que alteram o tamanho da lista, ou de outra forma, que determinam uma perturbação tal que iterações em progresso podem apresentar resultados incorretos. Não está muito claro o que isso significa. Minha sugestão é que se evite quaisquer modificações na lista subjacente. A situação é complicada ainda mais pela possibilidade de múltiplas visões sobre a mesma coleção subjacente. Você pode ter múltiplos iteradores sobre a mesma lista, por exemplo. Neste caso, você deve considerar também iterações entre visões. E se você modificar a lista através de um de seus iteradores, os outros iteradores serão invalidados, e não deverão ser utilizados novamente. Existem algumas estratégias úteis que aliviam a complexidade das visões. Se você está utilizando uma visão, você deve considerar cuidadosamente os seguintes conselhos: · Você pode limitar o escopo dentro do qual a visão é acessível. Por exemplo, utilizando um loop do tipo for ao invés de uma sentença while, para se realizar a iteração. Desta forma, você estará limitando o escopo do iterador para o escopo do próprio loop. Esta prática torna muito mais fácil garantir que não ocorrerão interações não desejadas durante a iteração. Isto nem sempre é possível; o programa Tagger que iremos discutir mais adiante no curso altera um iterador a partir de um local a muitas invocações de métodos de distância, e em uma classe diferente, a partir do local de sua criação! · Você pode evitar a alteração de uma visão ou de um objeto subjacente através do recurso de wrapping através de métodos da classe Collection. Por exemplo, se você criar uma visão a partir do método keySet de um mapa, e não pretende modificá-la, você pode tornar o conjunto

imutável: Set s = map.keySey (); Set safe_s = Collections.unmodifiableSet (s);