Iteração da ArrayQueue e ArrayDeque PDF

Iteração da ArrayQueue e ArrayDeque Nas coleções estáticas ArrayQueue e ArrayDeque deparamo-nos com uma dificuldade adicional relacionada com a deteção do fim da iteração, dado estarem suportadas em arrays circulares. Em todas as coleções suportadas por arrays, a iteração chega ao fim...

Iteração da ArrayQueue e ArrayDeque Nas coleções estáticas ArrayQueue e ArrayDeque deparamo-nos com uma dificuldade adicional relacionada com a deteção do fim da iteração, dado estarem suportadas em arrays circulares. Em todas as coleções suportadas por arrays, a iteração chega ao fim quando o j se posiciona na célula a seguir ao último elemento da coleção essa é uma condição necessária e suficiente, tratando-se de um ArrayStack; mas já o não será, se estivermos a falar de uma ArrayQueue ou de uma ArrayDeque; estando em causa, nestas duas últimas coleções, um array circular, o j encontrar-se na célula a seguir ao último elemento pode não significar que se tenha chegado ao fim da iteração; pode, pelo contrário, significar que apenas se está a iniciar a iteração, uma vez que, se o array estiver cheio, essa também é a posição do 1º elemento (ver ilustração do diapositivo seguinte). Desambiguação do teste de fim de iteração nas coleções ArrayQueue e ArrayDeque Se deixarmos o j avançar para a posição a seguir ao último elemento, o seu novo estado pode efetivamente ser confundido com o início da fila (basta que o array esteja completamente ocupado), deixando de ser possível perceber-se posteriormente se a iteração terminou ou se apenas estará a começar; Para que o j não assuma então esse estado com significado ambíguo, devemos evitar que ele passe do último elemento para a posição seguinte nessa situação, devemos forçar a que tome um valor inválido, por exemplo -1, para que esse seu novo estado não deixe dúvidas quanto ao seu verdadeiro significado; na próxima invocação do hasNext(), facilmente se perceberá em que estado se encontra o j e o próprio iterador. Segue-se a definição do tipo de iterador a usar nas coleções ArrayQueue e ArrayDeque, implementada de acordo com a solução descrita. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 58  Iteração num array circular cheio Quando j=2, em que estado se encontra o iterador? Acabou de terminar a sua iteração N-1 0 ou estará apenas a começar? 1 f=2 iterador Array circular, j=2 quando completamente preenchido qualquer semelhança com algo que já nos é familiar é mera coincidência Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 59  Tipo de iterador para as coleções ArrayQueue e ArrayDeque Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 60  Tornar a coleção LinkedStack iterável Como sabemos, na LinkedStack, em vez de um array, é usada uma lista ligada como estrutura de suporte ou, mais precisamente, uma instância da classe SinglyLinkedList, a qual mantém todo o seu conteúdo privado, algo que dificulta a tarefa da coleção LinkedStack, uma vez que para implementar as operações necessárias à iteração, precisa de aceder aos nodos (privados) da lista ligada; uma possível solução passa por tornar a própria lista ligada iterável esta parece ser uma opção inteligente uma vez que vai tornar bastante simples a criação de todas as coleções inteiráveis que tenham por base a lista ligada em causa. Método imposto pela interface Iterable, da qual passou a derivar a interface Stack. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 61  Tornar a lista ligada, ela própria, iterável A LinkedQueue, sendo baseada na mesma SLL, bastará que lhe adicionemos o método iterator(), para fique tb iterável Tornar a LinkedDeque iterável passará também por tornar iterável a lista duplamente ligada (DLL) que lhe dá suporte a qual deverá passar a incluir a classe do iterador DLLIterator (muito parecida com a classe SLLIterator). Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 62  Exemplo de utilização de iteradores Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 63 Implementação de Dicionários Maps Algoritmos e Estrutura de Dados 64  Listas com acesso apenas pelos extremos?… Dispomos já de duas listas ligadas, as quais representam duas importantes estruturas de dados dinâmicas, de grande utilidade no suporte a coleções do tipo linear. Porém, essas duas estruturas foram projetadas para servirem de suporte a três tipos de coleções (stacks, queues, deques), que apresentam em comum a particularidade dos seus elementos serem inseridos, removidos e consultados sempre pelos extremos da coleção. Mas excluindo estes 3 tipos de coleções, por norma o acesso aos elementos não está condicionado aos extremos na maior parte das coleções, deve ser possível remover ou consultar elementos interiores da coleção; é o que acontece precisamente nos dicionários nos dicionários, parte das operações são realizadas sobre o elemento identificado por uma dada chave, elemento esse que estará muito provavelmente numa posição intermédia da coleção; e para garantir eficiência na pesquisa dum elemento dada a sua chave, por norma os dicionários são coleções ordenadas tratando-se de coleções ordenadas, então também a inserção dum novo elemento deve acontecer numa posição bem determinada da coleção (e não apenas nos extremos), para que a ordenação não fique comprometida. Tornar a própria lista ligada ordenada será a solução adequada para o suporte dinâmico quer dos dicionários quer doutras coleções ordenadas. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 65  Listas Ligadas Ordenadas De forma a dispormos de uma estrutura de dados dinâmica mais versátil de suporte, que possa vir então a a ser usada na construção doutro tipo de coleções, passaremos, de seguida, a implementar a classe genérica SortedDoublyLinkedList, a qual representará uma lista duplamente ligada ordenada tratando-se de uma lista duplamente ligada, a mesma será criada por derivação da classe DoublyLinkedList necessitando de manter ordenados os seus elementos, deveria implementar os mecanismos que possibilitem a comparação dos elementos, quer pela sua ordem intrínseca, quer com o auxílio dum objeto comparador; Porém, visando soluções mais simples, vamos sempre nas nossas coleções comparar os seus elementos pela ordem intrínseca dos mesmos, exigindo, para o efeito, que o parâmetro E represente sempre uma classe comparável. todos os seus métodos devem ter sempre em conta a ordenação dos elementos; se estiverem por ordem crescente: o método de inserção coloca o elemento imediatamente antes do 1º elemento igual ou superior a ele; qualquer método que precise de localizar um elemento apenas o procura até encontrar o 1º elemento igual ou superior a ele. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 66  Preparar a Lista Duplamente Ligada… De modo a podermos derivar da lista duplamente ligada (DLL) a classe que defina uma DLL ordenada, é necessário fazer-lhe alguns ajustes… public class DoublyLinkedList implements Iterable{ protected static class Node { //passou-se de private para protected... // restante código //adicionou-se o próximo método public void setElement(E e) { element = e; } } protected Node header; //passou-se de private para protected protected Node trailer; //passou-se de private para protected... // restante código //passou-se o próximo método de private para protected protected void addBetween(E e,Node predecessor,Node successor) {… //passou-se o próximo método de private para protected protected E remove(Node node) {...... // restante código } Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 67  Definição duma Lista Duplamente Ligada Ordenada [1/4] Como dissemos, de forma a simplificarmos as nossas implementações, vamos exigir que os elementos a colecionar (do tipo E) sejam comparáveis entre si, que será o mesmo que dizer que a classe representada pelo parâmetro tipo E tem que implementar a interface Comparable Felizmente, o Java permite-nos impor este tipo de restrição através da seguinte declaração do parâmetro tipo de uma qualquer classe XPTO genérica: public class XPTO {... Repare-se que, neste contexto, a palavra extends é usada em sentido lato, podendo significar que a classe E estende Comparable (caso Comparable fosse uma classe) ou que a classe E implementa Comparable (no caso presente); Com esta restrição, fica assegurado que a classe genérica XPTO apenas pode ser instanciada (concretizada) se se usar para parâmetro E uma classe comparável; Dessa forma, dentro da classe XPTO o compilador Java já nos permite que invoquemos o método compareTo() de um qualquer objeto do tipo E. public class SortedDoublyLinkedList extends DoublyLinkedList{... //continua Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 68  Definição duma Lista Duplamente Ligada Ordenada [2/4] public class SortedDoublyLinkedList extends DoublyLinkedList{ private Node ceilingNode(E e) { Node n= header.getNext(); while(n!=trailer && e.compareTo(n.getElement())>0) n=n.getNext(); return n; } public E find(E e) { Node n = ceilingNode(e); if(n!=trailer && e.compareTo(n.getElement())==0) return n.getElement(); else return null; 2 10 15 30 } ceilingNode(.) ceilingNode(.) ceilingNode(.) ceilingNode(.)... //continua header trailer null 3 5 10 20 25 null Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 69  Definição duma Lista Duplamente Ligada Ordenada [3/4] public class SortedDoublyLinkedList extends DoublyLinkedList{... //código anterior // public update methods public void add(E e) { Node n= ceilingNode(e); addBetween(e, n.getPrev(), n); // place just before the n 2 10 15 30 } ceilingNode(.) ceilingNode(.) ceilingNode(.) ceilingNode(.) //Disabling inherited methods header trailer @Override null 3 5 10 20 25 null public void addFirst(E e) { throw new UnsupportedOperationException("Método de inserção não permitido numa lista ordenada."); } @Override public void addLast(E e) { throw new UnsupportedOperationException("Método de inserção não permitido numa lista ordenada."); }... de Implementação //continua estruturas de dados lineares Algoritmos e Estrutura de Dados 70  Definição duma Lista Duplamente Ligada Ordenada [4/4] public class SortedDoublyLinkedList extends DoublyLinkedList{... //código anterior public E put(E e) { 2 10 15 30 Node n= ceilingNode(e); ceilingNode(.) ceilingNode(.) ceilingNode(.) ceilingNode(.) if(n!=trailer && e.compareTo(n.getElement())==0){ E old=n.getElement(); header trailer n.setElement(e); null 3 5 10 20 25 null return old; }else{ addBetween(e, n.getPrev(), n); // place just before the n return null; } } public E remove(E e) { Node n = ceilingNode(e); if(n!=trailer && e.compareTo(n.getElement())==0) return remove(n); else return null; } Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 71 }  Lista Duplamente Ligada Ordenada Iterável Como nota final, refira-se que a classe SortedDoublyLinkedList, que se acabou de criar, já é uma estrutura iterável Como deriva da DoublyLinkedList, já herda dela o mecanismo de iteração necessário isto é, assume-se (por herança) como implementadora da interface Iterable e herda o método iterator() já implementado. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 72  Implementação de um dicionário Um dicionário é uma coleção de pares chave/valor como tal, se for suportado por uma lista ligada, cada um dos seus nodos deve conter, como elemento, um objeto que guarde em si quer a chave quer o valor designaremos a classe desse objeto por Entry (entrada), que representará então um par chave/valor tratar-se-á de uma classe genérica, com parâmetros K e V, representando, respetivamente, o tipo de chave e o tipo de valor a acomodar; necessariamente comparável, dado que será usada como parâmetro E da lista ordenada SortedDoublyLinkedList, que impõe essa restrição; e definida como classe interna da coleção. SortedDoublyLinkedList header trailer key key null null value value null null Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 73  Versão simplificada da interface Map Comecemos por definir a interface para um qualquer dicionário, que será uma versão simplificada da interface Map do Java (que integra a JCF). public interface Map { int size( ); boolean isEmpty( ); V get(K key); V put(K key, V value); V remove(K key); Iterable keySet( ); } Antes de avançarmos já para a definição da classe com a versão final do nosso dicionário, de forma a imitarmos um pouco a estrutura de classes da JCF, vamos, desta vez, optar por definir previamente uma classe abstrata intermédia, que terá como missão fornecer funcionalidades comuns aos diferentes tipos de dicionários, que dela venham a derivar no fundo, esta classe implementa parcialmente a interface Map, definindo todos os métodos e outros elementos que não dependam da implementação concreta da coleção, podendo ainda acrescentar novas funcionalidades; evitando, dessa forma, que os mesmos métodos e funcionalidades tenham que ser implementadas em cada uma das coleções concretas. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 74  A classe abstrata AbstractMap public abstract class AbstractMap implements Map { public boolean isEmpty( ) { return size() == 0; } //---------------- Definição de classes internas ---------------- protected static class Entry implements Comparable{ //permite embrulhar num único objeto o par K/V private K k; // key private V v; // value public Entry(K key, V value) { k = key; v = value; } public K getKey( ) { return k; } public V getValue( ) { return v; } public void setKey(K key) { k = key; } public V setValue(V value){ V old = v; v = value; return old; } public int compareTo(Entry outra){return k.compareTo(outra.k); } } //----------- end of nested Entry class ----------- } Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 75  AbstractMap Como se constata no código do diapositivo anterior, a classe Entry é comparável (implementa a interface Comparable), para que objetos desse tipo possam vir a ser colecionados pela lista ordenada, que impõe essa restrição. Por sua vez, e como se pode verificar no mesmo código, as ‘entries’ são comparadas de acordo com as chaves que guardam Sendo por isso também necessário que as próprias chaves sejam igualmente comparáveis. Daí a restrição imposta ao parâmetro tipo K:... Entry... Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 76  A classe LinkedMap [1/3] public class LinkedMap extends AbstractMap { private SortedDoublyLinkedList list; public LinkedMap(){ list = new SortedDoublyLinkedList(); } public int size() {return list.size(); } list header trailer... //continua null 3 5 5 10 20 20 25 null val1 val2 val3 val4 val5 Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 77  A classe LinkedMap [2/3] public class LinkedMap extends AbstractMap { private SortedDoublyLinkedList list;... //código anterior public V get(K key) { Entry e=new Entry(key,null); Entry f=list.find(e); if(f==null) return null; else return f.getValue(); } public V put(K key, V value) { Entry e=new Entry(key,value); Entry f=list.put(e); if(f==null) return null; else return f.getValue(); } public V remove(K key) { Entry e=new Entry(key,null); Entry f=list.remove(e); if(f==null) return null; list else return f.getValue(); header trailer } null 3 val1 5 5 val2 10 val3 20 20 val4 25 val5 null... //continua Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 78  A classe LinkedMap [3/3] public class LinkedMap extends AbstractMap { private SortedDoublyLinkedList list;... //código anterior // Support for public keySet method... private class KeyIterator implements Iterator { //tipo de iterador de chaves private Iterator it = list.iterator( ); public boolean hasNext( ) { return it.hasNext( ); } public K next( ) { return it.next( ).getKey( ); } // return key! } private class KeyIterable implements Iterable { public Iterator iterator( ) { return new KeyIterator( ); } } public Iterable keySet( ) { return new KeyIterable( ); } } // fim da classe LinkedMap list header trailer null 3 5 5 10 20 20 25 null val1 val2 val3 val4 val5 Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 79 Implementação de um dicionário baseado num array Segue-se a definição completa da classe genérica que implementa um dicionário de natureza estática sendo, por isso, baseado num array; deriva, naturalmente, da classe AbstractMap, de forma a aproveitar as funcionalidades nela já implementadas; e opta-se, também neste caso, por manter os elementos ordenados, pelo valor das chaves, sendo, por isso, a classe K das chaves a ter que que ser comparável (a implementar a interface Comparable) Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 80  A classe ArrayMap [1/5] public class ArrayMap extends AbstractMap { private static final int CAPACITY=1000; // default array capacity private Entry[ ] data; // array used for storage of entries private int sz = 0; // size private int compKE(K key, Entry e){ //método auxiliar que compara return key.compareTo(e.getKey()); //uma chave com uma Entry } public ArrayMap( ) { this(CAPACITY); } // constructs map with default capacity public ArrayMap(int capacity) { // constructs map with given capacity data = (Entry[ ]) new Entry[capacity]; }... //continua Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 81  A classe ArrayMap [2/5] public class ArrayMap extends AbstractMap {... //código anterior public int size( ) { return sz; } private int ceilingEntry(K key){ //devolve a posição da Entry com a menor chave int i; //que seja maior ou igual a key for(i=0; i0; i++); return i; 2 10 15 30 } ceilingEntry(.) ceilingEntry(.) ceilingEntry(.) ceilingEntry(.) public V get(K key) { data 33 val1 55 val2 10 10 val3 20 20 val4 25 25 val5 int i=ceilingEntry(key); 0 1 2 3 4 sz=5 if(i==sz) return null; else if(compKE(key,data[i])==0) return data[i].getValue(); else return null; }... //continua Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 82  A classe ArrayMap [3/5] public class ArrayMap extends AbstractMap {... //código anterior 2 10 15 30 ceilingEntry(.) ceilingEntry(.) ceilingEntry(.) ceilingEntry(.) public V put(K key, V value) { if(size()==data.length && get(key)==null) throw new IllegalStateException("Map is full"); Entry e=new Entry(key,value); data 33 val1 55 val2 10 10 val3 20 20 val4 25 25 val5 int i=ceilingEntry(key); //i: posição de inserção 0 1 2 3 4 sz=5 V old=null; //objeto a devolver (o que tem a chave igual a key, ou null se não existir) if(i=i+1; k--) data[k]=data[k-1];//Desloca para a direita as //entries a partir da pos. i data[i]=e; if(old==null) sz++; //Se a chave ainda não existia, contabilizamos mais 1 elemento return old; }... //continua Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 83  A classe ArrayMap [4/5] public class ArrayMap extends AbstractMap {... //código anterior public V remove(K key) { if (isEmpty()) return null; int i=ceilingEntry(key); if(i