14. Interfaces; Listas e cadeias ligadas; Iteradores – Fundamentos de Programação

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();}


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; } …}


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


«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)


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?


Lista genérica?

public class ArrayList { private Object[] items;

…}


- items

*ObjectArrayList

Room

Lista genérica: implementação

public class ArrayList<Item> { private Item[] items;

…}


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()); }

}


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


LinkedListItem

NodeItem

- nextNode: Node- item: Item

LinkedListItem

- firstNode: Node<Item>- currentNode: Node<Item>

NodeItem


Notações para o embutimento.

LinkedList::NodeItem


LinkedListItem

- firstNode: Node<Item>- currentNode: Node<Item>

Lista ligada genérica: utilização


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)); }


}


Inserir novo elemento no início ou no meio da lista não implica «empurrar» elementos existentes!

Lista ligada genérica: Exemplo


rooms : LinkedList<Item →

Room>

: Node<Item → Room>

firstNode currentNodenextNode

item item

nextNode = null

: Room


: Room

Lista ligada genérica: inserir no início


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); } …}


Lista ligada genérica: inserir no início



Room>



item item

nextNode = null

: Room


: RoomnewItem : Room


nextNode

item

firstNode

Lista ligada genérica: remover do início


…

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



Room>



item item

nextNode = null

: Room


: Room

item = null

nextFirstNode : «ref» Node<Item → Room>

firstNode

Lista ligada genérica: inserir no fim


…

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; }

…}




…

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); } }

…}





Room>



item item

nextNode = null

: Room


: Room

lastNode : «ref» Node<Item → Room>

nextNode = null


nextNode

newItem : Roomitem

Lista ligada genérica: passar ao seguinte


…

public Item next() { if (!hasNext()) throw new NoSuchElementException("…");

if (currentNode == null) currentNode = firstNode; else currentNode = currentNode.nextNode;

return currentNode.item; }

…}


Lista ligada genérica: passar ao seguinte



Room>



item item

: Room


: Room

nextNode = null


nextNode

item

currentNode

: Room



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 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()); }

}






public void show() { Iterator<Room> i = rooms.iterator(); while(i.hasNext()) out.println(i.next()); }

}


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.



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






public void show() { for (Room room : rooms) out.println(room); }

}


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

Education

14. Interfaces; Listas e cadeias ligadas; Iteradores – Fundamentos de Programação