ProgramaçãoporObjectos Java - Autenticação · LEEC@IST Java – 2/83 Introdução (1) ... elemento, resultando em acessos muito rápidos. • Bons para insertsearche delete, mas

LEEC@IST Java – 1/83

Programação por Objectos

Java

Parte 9: Classes utilitárias


Introdução (1)

• O Java disponibiliza um conjunto de classes utilitárias:

– com funcionalidades importantes para o programador.

– distribuídas no ambiente de desenvolvimento empacotes (dentro do arquivo src.zip)• src/java/lang # classes de linguagem (Integer,…)

» importado automaticamente

• src/java/util # utilitários diversos (Vector,…)

• src/java/math # classe Math

• src/java/io # classes entrada/saída


Introdução (2)

• O J2SE disponibiliza diversos grupos de interfaces. Neste capítulo abordamos 4:1. Comparator e Comparable – descrevem comparações

entre objectos (por exemplo, para ordenação).2. Collection – descrevem colecções de objectos.3. Map – descrevem funções entre objectos.4. Iterator – descrevem varrimentos sobre colecções de

objectos, sem conhecer a forma como estão organizados.

• O código das classes pode ser consultado emhttp://www.docjar.com


Introdução (3)Hierarquia geral das interfaces de ADTs no J2SE 5

<<interface>>

Collection

<<interface>>

Queue

<<interface>>

Set

<<interface>>

SortedSet

<<interface>>

List

<<interface>>

Iterable

E

E

EE

E

E


Introdução (4)

<<interface>>

Iterator

<<interface>>

ListIterator

<<interface>>

Map

<<interface>>

SortedMap

<<interface>>

ConcurentMap

K,VE

E K,V

Hierarquia geral das interfaces de ADTs no J2SE 5

K,V


Ordenação (1)

• Classes que envolvem ordenação implementam umade duas interfaces:– Comparable

– Comparator


Interface Comparable (1)

• Usada quando existe uma ordem natural (ex: Character, Integer, Date).

• Implementada dentro da classe pelo métodoCompareTo, que implica ordem total dentro da classe.

• Mais simples de implementar, mas menos flexível(que a interface Comparator).



• Valor retornado pelo compareTo deve ser:< 0 se o objecto sobre o qual o método é chamado é menor

que objecto recebido como parâmetro= 0 se o objecto sobre o qual o método é chamado e o

objecto recebido como parâmetro são iguais porequivalência (equals)

> 0 caso contrário

public interface Comparable<T> {

public int compareTo(T other);

}



public class Conta implements Comparable<Conta> {private static long numProxConta = 0;protected long numConta; // número da contaprotected float quantia; // saldo actual//...public boolean equals(Object obj) {

return numConta==((Conta)obj).numConta;}public int compareTo(Conta other) {

if (numConta > other.numConta) return 1;

else if (numConta == other.numConta) return 0;

else return -1;

}

//...}



Conta mc = new Conta(“Manuel Silva”,1000);Conta outra = new Conta(“Luís Silva”,200);System.out.println(mc.compareTo(mc));System.out.println(mc.compareTo(outra));System.out.println(outra.compareTo(mc));

No terminal é impresso 0

1-1



• As interfaces são tipos, por isso podemos ter:

• É possível definir, por exemplo, um algoritmo de ordenação para ordenar uma tabela de objectos Comparable (sem olhar a que classe é que esses objectos pertencem):

Comparable<Conta> cc;

class Ordena { static Comparable<?>[] ordena(Comparable<?>[] objs) {

// detalhes da ordenação ... return objs;

} }


• A classe java.util.Arrays oferece um método que permite ordenar objectos numa tabela de Object segundo a sua ordenação natural:

public static void sort(Object[] a, int fromIndex, int toIndex)

– Ordena os objectos da tabela a do índice fromIndex(inclusivé) ao índice toIndex (exclusivé).

– Todos os elementos da tabela no intervalo [fromIndex, toIndex] têm de implementar a interface Comparable.

– Todos os elementos nesse intervalo têm de ser mutuamente comparáveis (i.e., obj1.compareTo(obj2)não deve lançar uma excepção ClassCastException).




public class Ordena {static Comparable<?>[] ordena(Comparable<?>[] objs) {

Comparable<?>[] res = new Comparable<?>[objs.length];System.arraycopy(objs, 0, res, 0, objs.length);java.util.Arrays.sort(res, 0, res.length);

return res;}

}

Conta mc = new Conta(“Manuel Silva”,1000);Conta outra = new Conta(“Luís Silva”,200);Comparable<?>[] contas = new Comparable<?>[2];contas[0]=outra;contas[1]=mc;contas = Ordena.ordena(contas);


Interface Comparator (1)

• Usada quando existe uma ordem dependente daaplicação (ex: ordenação de uma lista de alunospode ser feita por nome, por número ou pelaclassificação).

• Implementada fora da classe (mas pode usarcompareTo sobre os atributos da classe), concretizando a interface Comparator.

• Implementação mais complexa, mas mais potente(que a interface Comparable).



• Valor retornado pelo compare deve ser:

< 0 se o objecto o1 é menor que objecto o2

= 0 se o objecto o1 é igual ao objecto o2

> 0 caso contrário

public interface Comparator<T> {

public int compare(T o1, T o2);

}



• Características do método compare:– sgn(compare(x,y)) == -sgn(compare(y,x))

para todo x, y.

– Transitividade: ((compare(x,y)>0) && (compare(y,z)>0))implica compare(x,z)>0.

– compare(x,y)==0implica sgn(compare(x,z)) == sgn(compare(y,z))para todo z.

– Inconsistência com equals: não é necessário que (compare(x,y)==0) == (x.equals(y)).



import java.util.Comparator;public class ComparadorContaPorSaldo implements Comparator<Conta> {

public int compare(Conta o1, Conta o2) { if (o1.quantia > o2.quantia) return 1; else if (o1.quantia == o2.quantia) return 0;else return -1;

} }

• Apesar de não fazer sentido definir uma ordenação natural de contas por saldo, pode ser necessário algures numa aplicação ordenar contas por saldo...



• A classe java.util.Arrays oferece um método genérico que permite ordenar objectos numa tabela segundo a ordem induzida por um Comparator:

public static <T> void sort(

T[] a, int fromIndex, int toIndex,

Comparator<? super T> c)

– Ordena os objectos da tabela a do índice fromIndex(inclusivé) ao índice toIndex (exclusivé).

– Todos os elementos nesse intervalo têm de ser mutuamentecomparáveis pelo Comparator (i.e., obj1.compare(obj2) não deve lançar uma excepçãoClassCastException).



Conta[] contas = new Conta[2];Contas[0] = new Conta(“Manuel Silva”,1000);Contas[1] = new Conta(“Luís Silva”,200);java.util.Arrays.sort(

contas, 0, contas.length,

new ComparadorContaPorSaldo());

• Uma tabela de contas poderia então ser ordenada por saldo da seguinte forma:



import java.util.Comparator;public class ComparadorEstudantePorNome

implements Comparator<Estudante> {public int compare(Estudante o1, Estudante o2) {

String nome1 = o1.primeiroNome();String nome2 = o2.primeiroNome();if (nome1.equals(nome2)) {

nome1 = o1.últimoNome();nome2 = o2.últimoNome();return nome1.compareTo(nome2);

} else return nome1.compareTo(nome2);}

}

• Dada uma lista de estudantes, o critério natural de ordenação seria por número de estudante. Para ordenar uma tal lista por nome:



public static void main(String[] args) {Estudante[] estudantes = new Estudante[args.length];for(int i=args.length-1; i>=0; i--)

estudantes[i] = new Estudante(args[i]);imprimirEstudantes(estudantes);System.out.println("*** Ordenado por nome ***");java.util.Arrays.sort(estudantes,

new ComparadorEstudantePorNome());

imprimirEstudantes(estudantes);}



• Se se pretender ordenar a tabela de estudantes por outro critério, por exemplo, por nota, basta desenvolver outra implementação de Comparable e chamar o método java.util.Arrays.sort.

System.out.println("*** Ordenado por nota ***");java.util.Arrays.sort(estudantes,

new ComparadorEstudantePorNota());


Interface Iterator

• A interface Iterator deve ser implementada porclasses que pretendam iterar sobre os seuselementos, um por um.

public interface Iterator<E> {

boolean hasNext();

E next();

void remove();

}


Interface Iterable

• Uma classe que implemente a interface Iterableoferece um Iterator que depois pode ser usadono ciclo for-each.

public interface Iterable<E> {

Iterator<E> iterator();

}


Interface Collection (1)

• Uma colecção, ou contentor, é um objecto queagrupa diversos objectos (eventualmente repetidos) numa unidade.

• Protótipos de métodos agrupados por três tipos:

– Operações básicas.

– Operações de manipulação a todos os elementosde uma só vez (bulk).

– Operações que convertem elementos numatabela.


Interface Collection (2)public interface Collection<E> extends Iterable<E> {

// Basic operations

int size();

boolean isEmpty();

boolean contains(Object elem);

boolean add(E elem);

boolean remove(Object elem);

Iterator<E> iterator();

// Bulk operations

boolean containsAll(Collection<?> coll);

boolean addAll(Collection<? extends E> coll);

boolean removeAll(Collection<?> coll);

boolean retainAll(Collection<?> coll);

void clear();

// Array operations

Object[] toArray();

<T> T[] toArray(T dest[]);

}



• Todos os métodos que necessitam de verificar igualdade entre objectos utilizam a igualdade por equivalência, baseada no equals (contains, add, remove, containsAll, addAll,removeAll e retainAll).

• A interface Collection não faz qualquer restrição a que elementos null sejam adicionados à colecção.



public class RemoverStringsCurtas {public static void remover(Collection<String> c){

// elimina strings unitárias ou nulasfor (Iterator<String> i=c.iterator(); i.hasNext(); )

if (i.next().length()<2) i.remove();

}}

• Pode usar-se um ciclo for e os métodos da interface Iteratorpara varrer os objectos de uma colecção:

– É possível adicionar e remover (add e remove) objectos àcolecção durante o varrimento.

– É possível alterar os objectos da colecção durante o varrimento.

– É possível iterar sobre múltiplas colecções.



• O varrimento pode ser facilitado com a instrução for-each:– A vantagem do for-each é puramente sintática.– Não é possível adicionar e remover (add e remove) objectos à

colecção durante o varrimento.

– É possível alterar os objectos da colecção durante o varrimento.

– Não é possível iterar sobre múltiplas colecções.

public class ImprimirStringsCurtas {public static void imprimir(Collection<String> c){

for(String s:c) if (s.length()<2)

System.out.println(s);}

}



• Da interface Collection são derivadas outras interfaces:– Set : colecção sem duplicações

– List : lista de elementos

– Queue : fila de elementos



<<abstract>>AbstractCollection

E<<interface>>

Collection

<<interface>>

Iterable

E

E

<<abstract>>AbstractSet

E <<abstract>>AbstractList

E <<abstract>>AbstractQueue

E

<<interface>>

Queue

<<interface>>

Set

<<interface>>

List

EE E


Implementação de interfaces (1)

• Existem diversas estruturas subjacentes de dados para implementar interfaces:1. Lineares: os objectos são ordenados por

posições, cada objecto tem apenas um predecessor (excepto primeiro) e um sucessor(excepto último).

2. Hierárquicas: cada objecto tem um únicopredecessor (excepto a raíz) e pode ter um número fixo de sucessores.

3. Desordenadas: não existe uma relação entredois objectos.


Implementação de interfaces (2)

• O J2SE 5 implementa as interfaces Set/List/Mappor intermédio de quatro estruturas de dados:– Tabelas de dispersão (hash tables).– Vectores de dimensão variável.– Árvores balanceadas.– Listas ligadas.

Set

List

Map

Hash Vector dim. var.

HashSet

---

HashMap

---

ArrayList

---

Árv. bal.

TreeSet

---

TreeMap

Lista Ligada

---

LinkedList

---

Estrutura de dados subjacente

Hash + Lista Ligada

LinkedHashSet

---

LinkedHashMap

Interfaces


Tabelas de dispersão(hash tables)

• Fazem o mapeamento de uma chave num valor.• As chaves são utilizadas para calcular inteiros (hash) que

devem ser diferentes para cada chave e estar uniformemente distribuídos (dispersos) pelo conjunto dos inteiros.

• Os pares chave valor são armazenados num conjunto de “baldes”. O balde correspondente a cada par chave tabela édeterminado directamente do hash (por exemplo utilizando os bits menos significativos).

• O número de baldes é fixo no na construção da tabela. Cada balde pode conter zero ou N chaves. A tabela deve ser dimensionada para cada balde conter tipicamente zero ou um elemento, resultando em acessos muito rápidos.

• Bons para insert search e delete, mas maus para funções de select e sort.

• Versões mais lista evitam ordem de iteração aleatória.


Arvores balanceadas

• Implementação de uma árvore Red-Black.

• Relacionadas com arvores 2-3-4 que garantem que a arvore se encontra exactamente balanceada em cada instante sem um aumento muito significativo do peso computacional.

• Exemplo de uma rotação à

esquerda em F para balancear

uma árvore.

F

D

GB

E

CA

F

D

G

B

ECA


Vectores de dimensão variável

• São re-alocados e copiados quando a sua capacidade excede determinado limite.


Interface Set (1)

<<interface>>

Set

<<interface>>

SortedSet

E

E

HashSet

E

LinkedHashSet

E

TreeSet

E

<<abstract>>AbstractSet

E


Interface Set (2)

• A interface Set não acrescenta nenhum método:

– Apenas define os mesmos métodos de Collection.

– São impostas restrições extra aos métodos adde equals, por forma a não haver elementos duplicados.


Interface Set (3)

• Algumas concretizações da interface Set:– HashSet: melhor, para a maioria das utilizações.

– LinkedHashSet: impõe ordem no Iterator (ordem de inserção).

– TreeSet: impõe ordem no Iterator (ordem natural ou ordem especificada por um objecto Comparator).

• É de evitar expor a implementação:Set s = new HashSet(); // preferível

HashSet s = new HashSet(); // a evitar!


Interface Set (4)

• Operações típicas sobre conjuntos:– União:

– Intersecção:

– Diferença:

– Subconjunto:

s1.addAll(s2); // s1 passa a união de s1 e s2

s1.retainAll(s2); // s1 passa a intersecção de s1 e s2

s1.removeAll(s2); // s1 passa a diferença de s1 e s2

s1.containsAll(s2); // testa se s2 é subconjunto de s1


Interface Set (5)

Collection comDuplicados;//...

• Truque para remover elementos duplicados de umacolecção:

Collection semDuplicados = new HashSet();semDuplicados.addAll(comDuplicados);

Collection semDuplicados = new HashSet(comDuplicados);


Interface Set (6)

Set<String> s1 = new HashSet<String>();s1.add("Ana"); s1.add("Joao"); System.out.print("s1 = "); imprimir(s1);

Set<String> s2 = new HashSet<String>();s2.add("Joao"); s2.add("Luis");System.out.print("s2 = "); imprimir(s2);

Set<String> s3;s3 = new HashSet<String>(s1); s3.addAll(s2);System.out.print("União(s1,s2) = "); imprimir(s3);s3 = new HashSet<String>(s1); s3.retainAll(s2);System.out.print("Intersecção(s1,s2) = "); imprimir(s3);s3 = new HashSet<String>(s1); s3.removeAll(s2);System.out.print("Diferença(s1,s2) = "); imprimir(s3);


Interface Set (7)

Relativamente ao exemplo anterior:

• O método estático imprimir imprime os elementosde um conjunto, por exemplo, com um iterador:static void imprimir(Collection<String> s) {...}

• No terminal é impresso:s1 = Joao Ana s2 = Joao Luis União(s1,s2) = Joao Luis Ana Intersecção(s1,s2) = Joao Diferença(s1,s2) = Ana


Interface List (1)

<<abstract>>AbstractList

<<abstract>>AbstractSequentialList

LinkedList<<interface>>

List

E

E

ArrayList Vector

Stack

E E E

E E

<<interface>>

Queue

E


Interface List (2)

public interface List<E> extends Collection<E> {

E get(int index);

E set(int index, E elem);

void add(int index, E elem);

E remove(int index);

int indexOf(Object elem);

int lastIndexOf(Object elem);

List<E> subList(int min, int max);

ListIterator<E> listIterator(int index);

ListIterator<E> listIterator();

}


Classe ArrayList (1)

• É uma implementação de List que guarda os seusobjectos numa tabela:– A tabela tem uma capacidade inicial.– Quando a capacidade inicial da tabela deixa de ser suficiente

é afectada uma nova tabela e o seu conteúdo é copiado.– Um valor correcto para a capacidade inicial da ArrayList

melhora o seu desempenho.

• Complexidade:– Adicionar (na posição i) e remover (da posição i): O(n-i) onde n é o tamanho da lista e i<n.• Adicionar (no fim) e remover (do fim): O(1)

– Aceder a um elemento (em qualquer posição): O(1)


Classe ArrayList (2)

public class ArrayList<E>

extends AbstractList<E>

implements List<E>, ...

{

ArrayList() {...}

ArrayList(int initialCapacity) {...}

ArrayList(Collection<? extends E> coll) {...}

void trimToSize() {...}

void ensureCapacity(int minCapacity) {...}

}

• Em caso de omissão, a capacidade inicial de um ArrayList é 10.


Classe LinkedList (1)

• É uma implementação de List como uma listaduplamente ligada.

• A classe LinkedList implementa ainda a interface Queue.

• Complexidade:– Adicionar (na posição i) e remover (da posição i): O(min{i,n-i}), onde n é o tamanho da lista.• Adicionar (no princípio ou fim) e remover (do princípio ou

fim): O(1).

– Aceder a um elemento na posição i: O(min{i,n-i}), onde n é o tamanho da lista.



• Da análise da complexidade podemos concluir que:– Deve ser usada uma LinkedList sempre que:

• Se tem uma lista cuja dimensão varia muito.

• É importante adicionar ou remover elementos numa posição arbitrária da lista.

– É preferível usar uma ArrayList sempre que:• Se quer uma lista cujos elementos são sempre adicionais no fim.

• Se quer aceder aos seus elementos de uma forma muito eficiente.



public class LinkedList<E>

extends AbstractSequentialList<E>

implements List<E>, Queue<E>, ...

{

LinkedList() {...}

LinkedList(Collection<? Extends E> coll) {...}

E getFirst() {...}

E getLast {...}

E removeFirst() {...}

E removeLast() {...}

void addFirst(E elem) {...}

void addLast(E elem) {...}

}


Classes de legado

• As interfaces/classes relacionadas com colecções apresentadas até aqui são novas no pacote java.util.

• O java.util sempre conteve outras colecções, que mantém por razões de compatibilidade de versões. Destacam-se:– Vector

– Stack

• Apesar de Vector e Stack serem classes de legado, implementam a interface List, logo funcionam como qualquer colecção.


Classe Vector (1)

public class Vector<E>

extends AbstractList<E>

implements List<E>, ...

{

//Métodod novos, tal como em ArrayList

Vector() {...}//ArrayList()

Vector(int initialCapacity) {...}//ArrayList(initialCapacity)

Vector(Collection<? Extends E> coll) {...}//ArrayList(coll)

void trimToSize() {...}

void ensureCapacity(int minCapacity) {...}

//... Diferença para ArrayList (próximo slide)

• Em caso de omissão, a capacidade inicial de um Vectoré 10.


Classe Vector (2)//Diferença para ArrayList

Vector(int initialCapacity, int capacityIncrement) {...}

void copyInto(Object[] anArray) {...}

int indexOf(Object elem, int index) {...}

int lastIndexOf(Object elem, int index) {...}

void setSize(int newSize) {...}

int capacity() {...}

//Métodos de legado com equivalência em ArrayList

void addElement(E elem) {...}//add(elem)

void insertElement(E elem, int index) {...}//add(index,elem)

void setElement(E elem, int index) {...}//set(index,elem)

void removeElement(int index) {...}//remove(index)

boolean removeElement(Object elem) {...}//remove(elem)

void removeAllElements() {...}//clear()

E elementAt(int index) {...}//get(index)

E firstElement() {...} //get(0)

E lastElement() {...} //get(size()-1)

}


Classe Vector (3)

• Utilização de Vector como classe de legado:

• Utilização de Vector como colecção genérica:

Vector vector = new Vector(20);

Vector<String> vector = new Vector<String>(20);

Vector<?> vector = new Vector<String>(20);


Classe Vector (4)import java.util.Vector;public class Main {

private final int SIZE = 10;private Vector vector = new Vector(SIZE);

//...public static void main(String[] args) {

Integer iobj;for(int index=0;index<SIZE;index++)

vector.addElement(new Integer(index));for(int index=2;index<SIZE;index+=2){

iobj=(Integer)vector.elementAt(index-1);vector.setElementAt(new Integer(2*iobj.intValue()),index);

}for(int index=0;index<SIZE;index++)

System.out.println(“Índice = “+index+“ “+vec.elementAt(index));

}}


Classe Vector (5)import java.util.Vector;public class Main {

private final int SIZE = 10;private Vector<Integer> vector = new Vector<Integer>(SIZE);

//...public static void main(String[] args) {

Integer iobj;for(int index=0;index<SIZE;index++)

vector.add(new Integer(index));for(int index=2;index<SIZE;index+=2){

iobj=(Integer)vector.get(index-1);vector.set(new Integer(2*iobj.intValue()),index);

}for(int index=0;index<SIZE;index++)

System.out.println(“Índice = “+index+“ “+vec.get(index));

}}


Classe Vector (6)

• A implementação genérica de Vectorpermite que chamar directamente os métodos da classe tipo.

• Exemplo:– Considere ContaOrdem e ContaPrazo

descendente da classe abstracta Conta.

– Na Conta é definido o método abstracto juro(), que é implementado nas classes concretas.


Classe Vector (7)

• O método juro() executa a implementação da classe concreta correspondente (ligação dinâmica).

• A criação de novas classes (de um subtipo de Conta) não requerem a alteração do código existente, facilitando a evolução das aplicações informáticas.

Vector<Conta> arquivo = new Vector<Conta>();//...arquivo.add(new ContaOrdem());arquivo.add(new ContaPrazo());//...for(i=0;i<arquivo.size();i++)

(arquivo.get(i)).juro();


Classe Stack

• A classe Stack é uma classe derivada de Vectorque adiciona métodos para obter uma estrutura de dados FIFO.

public class Stack<E> extends Vector<E> {

Stack();

E push(E item);

E pop();

E peek();

boolean empty();

int search(Object o);

}


Implementações de List

Vantagens– Resolvem o inconveniente da dimensão das tabelas não poderem ser alteradas após a instanciação.

Inconvenientes– Apenas podem armezenar objectos (dados de tipo primitivo têm de ser armazenados como objectos de embrulho).

– Acesso às tabelas é mais eficiente.


Classe Arrays (1)

• A classe estática Arrays é criada pelo J2SE e disponibiliza métodos para manipulação de tabelas.

• A grande maioria dos métodos têm váriassobreposições: – Uma para tabelas de cada tipo primitivo.– Uma para tabelas de Object.

• Os métodos são ainda disponibilizados em duasvariantes:– Uma actuando em toda a tabela.

– Outra actuando numa subtabela especificada por doisíndices.


Classe Arrays (2)

• Os métodos da classe Arrays são:– static void sort: Ordenação ascendente, com parâmetros:

1. Tabela a ordenar (obrigatório)

2. Dois índices, mínimo e máximo, que definem a subtabela (poromissão, é toda a tabela)

3. Um objecto Comparator, que induz ordem nos elementos databela (por omissão, ordem natural definida pelo Comparable)

– static int binarySearch: Procura binária (a tabela tem de estar ordenada em ordem ascendente), com parâmetros:

1. Tabela a procurar (obrigatório)

2. Valor a pesquisar (obrigatório)3. Um objecto Comparator, que induz ordem nos elementos da

tabela (por omissão, ordem natural definida pelo Comparable).


Classe Arrays (3)

Integer inteiros[] = new Integer[2];inteiros[0]=1;inteiros[1]=2;System.out.println(Arrays.binarySearch(inteiros,1)); inteiros[0]=2;inteiros[1]=1;System.out.println(Arrays.binarySearch(inteiros,1));

No terminal é impresso 0

-1


Classe Arrays (4)

– static void fill: Preenchimento de posições, com parâmetros:1. Tabela a preencher (obrigatório)

2. Dois índices, mínimo e máximo, que definem a subtabela (por omissão, é toda a tabela)

3. Valor a inserir (obrigatório)

– static boolean equals: Verifica igualdade por equivalência de duas tabelas, com parâmetros:1. Duas tabelas do mesmo tipo (obrigatório)

– static boolean deepEquals: Verifica igualdade por equivalência de tabelas aninhadas de qualquer dimensão, com parâmetros:1. Duas tabelas de tipo Object (obrigatório)


Classe Arrays (5)

– static int hashCode: devolve o código de dispersão da tabela recebida como parâmetro (baseada no seu conteúdo).

– static int deepHashCode: devolve o código de dispersão da tabela de tipo Object recebida como parâmetro (baseada no seu conteúdo, e tendo em consideração aninhamento).

– static String toString: devolve uma string que representa o conteúdo da tabela recebida como parâmetro.

– static String deepToString: devolve uma string que representa o conteúdo, tendo em consideração aninhamento, da tabela de tipo Object recebida como parâmetro.

– static <T> List<T> asList(T… t): devolve uma Listcom os elementos recebido como parâmetro.• Este método actua como uma ponte entre tabelas e colecções (para complementar o método toArray das colecções).


Classe Arrays (6)Integer inteiros[][] = new Integer[2][5];Arrays.fill(inteiros[0],0); Arrays.fill(inteiros[1],1);System.out.println("inteiros="+Arrays.deepToString(inteiros));Integer outro[][] = new Integer[2][5];Arrays.fill(outro[0],0); Arrays.fill(outro[1],1);System.out.println("outro="+Arrays.deepToString(outro));System.out.println(inteiros.hashCode()+"\t"+

Arrays.hashCode(inteiros)+"\t"+Arrays.hashCode(inteiros[0])+"\t"+Arrays.hashCode(inteiros[1])+"\t"+Arrays.deepHashCode(inteiros));

System.out.println(outro.hashCode()+"\t"+Arrays.hashCode(outro)+"\t"+Arrays.hashCode(outro[0])+"\t"+Arrays.hashCode(outro[1])+"\t"+Arrays.deepHashCode(outro));

No terminal é impresso inteiros=[[0, 0, 0, 0, 0], [1, 1, 1, 1, 1]]

outro=[[0, 0, 0, 0, 0], [1, 1, 1, 1, 1]]

16795905 922240875 28629151 29583456 917088098

12115735 676418749 28629151 29583456 917088098


Classe Arrays (7)

List lista = new ArrayList();

lista.add(1);lista.add("Hello");Object[] objectos = new Object[2];

objectos = lista.toArray();System.out.println(lista.equals(Arrays.asList(objectos))); System.out.println(objectos.equals(lista.toArray())); System.out.println(Arrays.equals(objectos,lista.toArray()));

No terminal é impresso true

falsetrue


Interface Queue (1)

<<interface>>Collection

<<interface>>Queue

<<abstract>>AbstractQueue

<<abstract>>AbstractCollection

PriorityQueue

E

E E

E

E


Interface Queue (2)

public interface Queue<E> extends Collection<E> {

E element(); // mostra a cabeça

E peek(); // mostra a cabeça ou null

E remove(); // mostre e remove a cabeça

E pool(); // mostra e remove a cabeça ou null

boolean offer(E elem); // insere elemento

}


Interface Queue (3)

• Apesar de as colecções aceitarem elementos nulos, uma Queue não deve ter elementos null, pois o null é usado no retorno dos métodos peek e pollpara indicar que a Queue está vazia.

• A class LinkedList é a implementação mais simples da interface Queue.– Por razões históricas são permitidos elementos null

numa LinkedList.

– Deve evitar-se inserir elementos null numa LinkedListsempre que esta for usada como uma Queue.


Classe PriorityQueue (1)

• A PriorityQueue é uma outra implementação de Queue.

• A implementação da PriorityQueue é baseada num acervo (heap).

• A cabeça da fila prioritária é o elemento menor que a fila contém.– O menor elemento é determinado pela ordem natural dos

elementos, ou indicado por um comparador entre dois elementos.

– Se o menor elemento representa o elemento com menor ou maior prioridade depende de como a ordem natural ou o comparador fornecido estão definidos.



• O iterador da PriorityQueue não varre necessariamente os elementos da fila por ordem de prioridade. Na realidade, o iterator segue a ordemde armazenamento no acervo.

• Apenas é garantido que remover elementos da fila prioritária ocorre por ordem de prioridade.


• Construtores de PriorityQueue:

• A capacidade é ilimitada, mas o ajustamento écomputacionalmente pesado.


public PriorityQueue()

public PriorityQueue(int initialCapacity)

public PriorityQueue(int initialCapacity, Comparator<? super E> comp)

public PriorityQueue(Collection<? extends E> coll)

public PriorityQueue(SortedSet<? extends E> coll)

public PriorityQueue(PriorityQueue<? extends E> coll)



public class Task {String name; // identificadorint level; // prioridade

public int level() {return level;

}public void newLevel(int value) {

level = value; }public Task(String name, int l) {

this.name=name;level = l;

}}



private static class TaskComparator implements Comparator<Task> {public int compare(Task l, Task r) {

return l.level() – r.level();}

}



PriorityQueue<Task> pq = new PriorityQueue<Task>(10,new TaskComparator());

Task t;for (char letter='A';letter<='G';letter++)

pq.add(new Task("Task "+letter,((letter-'A')%4));while (!pq.isEmpty()){

t=pq.poll();System.out.println(t.toString()+" priority=“+t.level());

}

No terminal é impresso: Tarefa A prioridade=0

Tarefa E prioridade=0Tarefa B prioridade=1Tarefa F prioridade=1Tarefa C prioridade=2Tarefa G prioridade=2Tarefa D prioridade=3


Interface Map (1)

• A interface Map<K,V> não estende a interface Collection.

• Principais caracteristicas dum Map<K,V>:– Não são adicionados elementos a um mapa,

mas sim um par chave/elemento.– Um mapa permite aceder a um valor dada uma

chave.– Uma chave mapeia zero ou um valor.– Um valor pode ser mapeado por várias chaves.

• Um mapa estabelece uma função parcial de chaves para valores.


Interface Map (2)

• Métodos básicos da interface Map<K,V>:int size();

boolean isEmpty();

boolean containsKey(Object key);

boolean containsValue(Object value);

V get(Object key);

V put(K key, V value);

V remove(Object key);

void putAll(Map<? extends K, ? extends V> otherMap)

void clear();


Interface Map (3)

• Alguns métodos para ver Map<K,V> comoCollection:

• Da interface Map são derivadas outras interfaces:

–SortedMap: chaves encontram-se ordenadas

–ConcurrentMap

Set<K> keySet();

Collection<V> values();


Classe HashMap (1)

• A classe HashMap é uma implementação dainterface Map por uma tabela de dispersão.

• O desempenho é muito bom.• Construtores da classe HashMap:

public HashMap(int initialCapacity, float loadFactor)

public HashMap(int initialCapacity)

public HashMap()

public HashMap(Map<? extends K, ? extends V> map)


Classe HashMap (2)import java.util.*;

String str;

Long l;

Map store = new HashMap(); // nome usado como chave

str = “Miguel”; l = new Long(1327);

store.put(str,l);

l = (Long) store.get(str);

if (l!=null)

System.out.println(“Codigo de ”+str+“=”+l.longValue());

str = “Luisa”; l = new Long(9261);

store.put(str,l);

l = (Long) store.get(str);

if (l!=null)

System.out.println(“Codigo de ”+str+“=”+l.longValue());


Interface SortedMap

interface SortedMap<K,V> extends Map<K,V> {

Comparator<? super K> comparator();

K firstKey();

K lastKey();

SortedMap<K,V> subMap(K minKey, K maxKey);

SortedMap<K,V> headMap(K maxKey);

SortedMap<K,V> tailMap(K minKey);

}


Class TreeMap

• A classe TreeMap é uma implementação dainterface SortedMap por uma árvore bináriabalanceada.– O acesso é menos eficiente.– Mas os elementos estão sempre ordenados.

• No programa exemplo de HashMap apenas se substitui a declaração: Map store = new TreeMap();

Documents

ProgramaçãoporObjectos Java - Autenticação · LEEC@IST Java – 2/83 Introdução (1) ... elemento, resultando em acessos muito rápidos. • Bons para insertsearche delete, mas