Apresentação 14
InterfacesListas e listas ligadasIteradores
Na aula anterior
Polimorfismo de subtipos Classes e operações polimórficas Herança Ligação estática e ligação dinâmica Classes abstractas e classes concretas Operações abstractas
Análise, desenho e implementação Dicionário do domínio Conceitos Conceitos concretos e conceitos abstractos
2013/2014 Fundamentos de Programação 2
Interfaces
Definem um comportamento que as classes podem implementar
Contêm apenas constantes e declarações de operações (e tipos embutidos)
Classes podem implementar interfaces
Uma classe pode implementar várias interfaces, embora possa derivar apenas de uma outra classe
Uma interface pode estender (derivar de) outra2013/2014 Fundamentos de Programação 3
Interfaces: definição
public interface Comparable<Type> { int compareTo(Type object);}
public interface Queue<Item> { Item element(); void add(Item item); void remove();}
2013/2014 Fundamentos de Programação 4
Operações apenas declaradas. Não se define qualquer método. Não é necessário usar o qualificador abstract.
Operações públicas por omissão.
Nota: A interface Queue é um pouco diferente na biblioteca do Java!
Interface genérica. Type é um parâmetro. O correspondente argumento tem de ser um tipo.
Interfaces: implementaçãopublic final class Rational implements Comparable<Rational> { private final int numerator; private final int denominator; … @Override public int compareTo(final Rational another) { final int leftNumerator = getNumerator() * another.getDenominator(); final int rightNumerator = another.getNumerator() * getDenominator();
if (leftNumerator > rightNumerator) return 1; if (leftNumerator < rightNumerator) return -1; return 0; } …}
2013/2014 Fundamentos de Programação 5
public final class Rational implements Comparable<Rational> { private final int numerator; private final int denominator; … public int compareTo(final Rational another){ … } …}
Implementação
Interfaces: implementação
2013/2014 Fundamentos de Programação 6
«interface»Comparable<Type →
Rational>
Rational
Relação de realização
Comparable<Type → Rational>
Rational
Interfaces: polimorfismo
public class CustomerQueue implements Queue<Customer> {
…
}
public class MyQueueTester {
…
public static void main(final String[] arguments) { Queue<Customer> customerQueue = new CustomerQueue();
… }
…
}2013/2014 Fundamentos de Programação 7
Queue<Item → Customer>
CustomerQueue
Interfaces: nomes
Adjectivo denotando possibilidade de realizar determinadas operações (e.g., Comparable)
Nome denotando conceito cujo comportamento será implementado (e.g., Queue)
2013/2014 Fundamentos de Programação 8
Caso semelhante ao das classes abstractas, mas1. não há qualquer herança de
implementação (i.e., de atributos não constantes e métodos) e
2. uma classe que implemente a interface pode simultaneamente implementar outras interfaces.
Genericidade
Precisa-se de classes semelhantes Com operações semelhantes Com atributos semelhantes Variando apenas em alguns tipos (e.g., o
tipo dos elementos a guardar em diferentes listas)
É necessário definir essas classes separadamente?
2013/2014 Fundamentos de Programação 9
Lista genérica?
public class ArrayList { private Object[] items;
…}
2013/2014 Fundamentos de Programação 10
- items
*ObjectArrayList
Room
Lista genérica: implementação
public class ArrayList<Item> { private Item[] items;
…}
2013/2014 Fundamentos de Programação 11
ArrayList<Item → Room>
Room*
- items
ArrayListItem
«bind» <Item → Room>
- items : Item [*]
Notação UML para classes genéricas (também conhecidas por modelos ou templates).
Classe genérica. Item é um parâmetro. O correspondente argumento tem de ser um tipo.
Lista genérica: utilização
public class Floor {
private ArrayList<Room> rooms = new ArrayList<Room>();
public Floor(final int numberOfRooms) { for (int roomNumber = 1; roomNumber != numberOfRooms + 1; roomNumber++) rooms.addFirst(new Room(roomNumber)); }
public void show() { while (rooms.hasNext()) out.println(rooms.next()); }
}
2013/2014 Fundamentos de Programação 12
Inserir novo elemento no início ou a meio da lista implica «empurrar» elementos existentes para «fazer espaço».
Para fazer isto o que é preciso?
Lista ligada genérica: implementação
public class LinkedList<Item> {
private Node<Item> firstNode = null; private Node<Item> currentNode = null; …
private static class Node<Item> {
private Node<Item> nextNode; private Item item;
private Node(final Node<Item> nextNode, final Item item) { this.nextNode = nextNode; this.item = item; }
} …}2013/2014 Fundamentos de Programação 13
Classe embutida (nested) privada. A classe LinkedList<Item> tem acesso aos membros privados de Node<Item>.
Lista ligada genérica: notação
2013/2014 Fundamentos de Programação 14
LinkedListItem
NodeItem
- nextNode: Node- item: Item
LinkedListItem
- firstNode: Node<Item>- currentNode: Node<Item>
NodeItem
- nextNode: Node- item: Item
Notações para o embutimento.
LinkedList::NodeItem
- nextNode: Node- item: Item
LinkedListItem
- firstNode: Node<Item>- currentNode: Node<Item>
Lista ligada genérica: utilização
public class Floor {
private LinkedList<Room> rooms = new LinkedList<Room>();
public Floor(final int numberOfRooms) { for (int roomNumber = 1; roomNumber != numberOfRooms + 1; roomNumber++) rooms.addFirst(new Room(roomNumber)); }
public void show() { while (rooms.hasNext()) out.println(rooms.next()); }
}
2013/2014 Fundamentos de Programação 15
Inserir novo elemento no início ou no meio da lista não implica «empurrar» elementos existentes!
Lista ligada genérica: Exemplo
2013/2014 Fundamentos de Programação 16
rooms : LinkedList<Item →
Room>
: Node<Item → Room>
firstNode currentNodenextNode
item item
nextNode = null
: Room
: Node<Item → Room>
: Room
Lista ligada genérica: inserir no início
public class LinkedList<Item> {
private Node<Item> firstNode = null; …
private static class Node<Item> { …
private Node(final Node<Item> nextNode, final Item item) { this.nextNode = nextNode; this.item = item; } }
public void addFirst(final Item newItem) { firstNode = new Node<Item>(firstNode, newItem); } …}
2013/2014 Fundamentos de Programação 17
Lista ligada genérica: inserir no início
2013/2014 Fundamentos de Programação 18
rooms : LinkedList<Item →
Room>
: Node<Item → Room>
firstNode currentNodenextNode
item item
nextNode = null
: Room
: Node<Item → Room>
: RoomnewItem : Room
: Node<Item → Room>
nextNode
item
firstNode
Lista ligada genérica: remover do início
public class LinkedList<Item> {
…
public void removeFirst() { if (isEmpty()) throw new NoSuchElementException(…);
if (currentNode == firstNode) currentNode = currentNode.nextNode;
Node<Item> nextFirstNode = firstNode.nextNode; firstNode.item = null; firstNode.nextNode = null; firstNode = nextFirstNode; }
…
}2013/2014 Fundamentos de Programação 19
Lista ligada genérica: remover do início
2013/2014 Fundamentos de Programação 20
rooms : LinkedList<Item →
Room>
: Node<Item → Room>
firstNode currentNodenextNode
item item
nextNode = null
: Room
: Node<Item → Room>
: Room
item = null
nextFirstNode : «ref» Node<Item → Room>
firstNode
Lista ligada genérica: inserir no fim
public class LinkedList<Item> {
…
public void addLast(final Item newItem) { if (firstNode == null) firstNode = new Node<Item>(null, newItem); else lastNode().nextNode = new Node<Item>(null, newItem); }
private Node<Item> lastNode() { Node<Item> node = firstNode;
while (node.nextNode != null) node = node.nextNode;
return node; }
…}
2013/2014 Fundamentos de Programação 21
Lista ligada genérica: inserir no fim
public class LinkedList<Item> {
…
public void addLast(final Item newItem) { if (firstNode == null) firstNode = new Node<Item>(null, newItem); else { Node<Item> lastNode = firstNode;
while (lastNode.nextNode != null) lastNode = lastNode.nextNode;
lastNode.nextNode = new Node<Item>(null, newItem); } }
…}
2013/2014 Fundamentos de Programação 22
Lista ligada genérica: inserir no fim
2013/2014 Fundamentos de Programação 23
rooms : LinkedList<Item →
Room>
: Node<Item → Room>
firstNode currentNodenextNode
item item
nextNode = null
: Room
: Node<Item → Room>
: Room
lastNode : «ref» Node<Item → Room>
nextNode = null
: Node<Item → Room>
nextNode
newItem : Roomitem
Lista ligada genérica: passar ao seguinte
public class LinkedList<Item> {
…
public Item next() { if (!hasNext()) throw new NoSuchElementException("…");
if (currentNode == null) currentNode = firstNode; else currentNode = currentNode.nextNode;
return currentNode.item; }
…}
2013/2014 Fundamentos de Programação 24
Lista ligada genérica: passar ao seguinte
2013/2014 Fundamentos de Programação 25
rooms : LinkedList<Item →
Room>
: Node<Item → Room>
firstNode currentNodenextNode
item item
: Room
: Node<Item → Room>
: Room
nextNode = null
: Node<Item → Room>
nextNode
item
currentNode
: Room
Lista ligada genérica: notação
2013/2014 Fundamentos de Programação 26
LinkedList
Item
Node
Item
- item: ItemnextNode
firstNode
currentNode 0..1
0..1
0..10..1
Esta solução não permite percorrer a lista mais do que uma vez em paralelo!
0..1
0..1
1
*
Lista ligada genérica: iteradores
public class Floor {
private LinkedList<Room> rooms = new LinkedList<Room>();
public Floor(final int numberOfRooms) { for (int roomNumber = 1; roomNumber != numberOfRooms + 1; roomNumber++) rooms.add(new Room(roomNumber)); }
public void show() { while (rooms.hasNext()) out.println(rooms.next()); }
}
2013/2014 Fundamentos de Programação 27
Lista ligada genérica: iteradores
public class Floor {
private LinkedList<Room> rooms = new LinkedList<Room>();
public Floor(final int numberOfRooms) { for (int roomNumber = 1; roomNumber != numberOfRooms + 1; roomNumber++) rooms.add(new Room(roomNumber)); }
public void show() { LinkedList<Room>.Iterator i = rooms.iterator(); while(i.hasNext()) out.println(i.next()); }
}
2013/2014 Fundamentos de Programação 28
Lista ligada genérica: iteradores
public class Floor {
private LinkedList<Room> rooms = new LinkedList<Room>();
public Floor(final int numberOfRooms) { for (int roomNumber = 1; roomNumber != numberOfRooms + 1; roomNumber++) rooms.add(new Room(roomNumber)); }
public void show() { Iterator<Room> i = rooms.iterator(); while(i.hasNext()) out.println(i.next()); }
}
2013/2014 Fundamentos de Programação 29
Iterator é umaclasse interna
(inner). As suas instâncias têm
uma ligação implícita à
instância da classe envolvente
que as criou. A ver com
pormenor mais tarde.
Lista ligada genérica: notação
2013/2014 Fundamentos de Programação 30
LinkedList
Item
Node
Item
- item: ItemnextNode
firstNode currentNode
0..10..1
0..1
Esta solução permite percorrer a lista mais do que uma vez em paralelo!
Iterator
LinkedList.this
*
0..1
0..1
*
*
1
Iteradores
Permitem iterar ao longo de uma sequência de elementos, actuando sobre essa sequência
A uma sequência podem associar-se vários iteradores
Classes que forneçam iteradores podem ser usadas em ciclos for-each…
… mas têm de implementar a interface Iterable
2013/2014 Fundamentos de Programação 31
Lista ligada genérica: iteradores
public class Floor {
private LinkedList<Room> rooms = new LinkedList<Room>();
public Floor(final int numberOfRooms) { for (int roomNumber = 1; roomNumber != numberOfRooms + 1; roomNumber++) rooms.add(new Room(roomNumber)); }
public void show() { for (Room room : rooms) out.println(room); }
}
2013/2014 Fundamentos de Programação 32
Mais tarde voltaremos a este assunto.
Fundamentos de Programação
A reter…
Interfaces Definem comportamentos (adjectivam) Classes implementam-nas
Listas Listas ligadas Operações sobre listas ligadas Introdução aos iteradores
2013/2014Página
33
Fundamentos de Programação
Sumário
Interfaces Listas e listas ligadas Iteradores
2013/2014Página
34