Universidade Federal de Minas Gerais
Instituto de Ciências Exatas
Departamento de Ciência da Computação

Observação: vários dos programas desta parte do material quando compilados irão resultar em um “aviso”:

C:\>javac sesnputil.java

Note: sesnputil.java uses unchecked or unsafe operations.

Note: Recompile with -Xlint:unchecked for details.

Trata-se do seguinte problema: nas edições Java 1.4 e anteriores as coleções e iteradores utilizavam a classe Object como tipo dos elementos que eram colecionados. A partir da edição Java 1.5 passou a existir na linguagem Java o suporte a “generics”. As classes relacionadas a coleções e iteradores foram reescritas para poder utilizar “generics” (ao invés de usar de maneira indiscriminada o tipo Object). Fica como tarefa de estudo para as férias o estudo e uso das classes de coleção e iteração das versões com suporte de “generics”:

http://java.sun.com/j2se/1.5/pdf/generics-tutorial.pdf

Coleções e iteradores

O ambiente Java (pacote java.util) dá suporte a diferentes implementações de coleções (Collection).

Considere o programa abaixo:

import java.util.*;

class sesnputil{
public static void main(String[] arg){
    Collection nd = new LinkedList();
    nd.add(new Integer(123));
    nd.add(new Integer(456));
    nd.add(new Integer(789));
    nd.add(new Integer(147));
    System.out.println("adicionou "+nd.size()+" itens");
    for(;nd.size()>0;){
      Iterator it= nd.iterator();
      for(;it.hasNext();){
        System.out.println(it.next());
      }
      it.remove();
      System.out.println("removeu ultimo. Tem "+nd.size()+" itens");
    }
}
}

Collection e Iterator são interfaces e existem várias implementações destas interfaces no ambiente Java. Vamos discutir de maneira simples e breve a hierarquia de interfaces e hierarquia de classes no pacote java.util (1.3)

List, Set e SortedSet são subinterfaces da interface Collection. List descreve o comportamento de seqüências ou listas. Listas tipicamente permitem elementos duplicados. A iteração sobre elementos de Collection é feita utilizando a interface Iterator enquanto que a iteração sobre elementos de uma List é feita utilizando a interface ListIterator. Set descreve o comportamento de conjuntos ou coleções que não permitem elementos duplicados. SortedSet descreve o comportamento de conjuntos cujos iteradores garantem alguma ordem. A iteração sobre elementos de Set e SortedSet é feita utilizando a interface Iterator.

Nenhuma classe implementa diretamente e na totalidade a interface Collection. Mas existe uma classe abstrata que a implementa: AbstractCollection. A interface List é implementada pelas classes LinkedList, ArrayList e Vector. A interface Set é implementada pela classe HashSet. A interface SortedSet é implementada pela classe TreeSet.

No programa acima utilizamos uma coleção do tipo Collection implementada pela classe LinkedList.

Exercícos

1. Mudar o programa acima para utilizar a implementação dada pela classe ArrayList.

2. Mudar o programa acima para utilizar uma coleção do tipo List (ao invés de Collection).

3. Mudar o programa acima para utilizar uma coleção do tipo Set (ao invés de Collection).

4. Faça um programa que verifica que a classe HashSet não aceita a adição (add) de elementos duplicados.

O restante do material abaixo discute implementações bem simples mas similares às implementações LinkedList e ArrayList. Observe que o código do método main é o mesmo em cada uma das implementações, exceto pela classe que implementa a interface Icolecao:

Icolecao nd = new ListaEncadeada();

Icolecao nd = new ListaArranjo();

Icolecao nd = new ListaEncadeadaNP();

Icolecao nd = new ListaEncadeadaDE();

As dimensões de implementação são muitas; usar ou não usar arranjos, usar ou não usar encadeamento, usar ou não usar nodos postiços, usar ou não usar encadeamento simples ou duplo, usar ou não usar valores primitivos ou somente referências (Object) etc.

Para simplificar ainda mais utilizamos as interfaces Icolecao e Iiterador ao invés de utilizar as interfaces Collection e Iterator do pacote java.util, além disso iremos trabalhar com valores do tipo int ao invés de trabalhar com referências para instâncias da classe Object (como acontece nas implementações de java.util).

A implementação abaixo é similar à implementação LinkedList.

import java.util.NoSuchElementException;

interface Iiterador{
boolean temProximo();
int proximo();
void remove();
}

interface Icolecao{
boolean adicione(int i);
Iiterador iterador();
void limpa();
boolean estaVazia();
int tamanho();
}

class ListaEncadeada implements Icolecao{

class IteradorLE implements Iiterador{

  Cnodo curr=inicio;
    Cnodo refAnt=null;
    public boolean temProximo(){
      return curr!=null;
    }
    public int proximo(){
      if(inicio==null|curr==null) throw new NoSuchElementException();
      refAnt=curr; /* marca nodo a ser removido */
      curr=curr.prox;
      return refAnt.info;
    }
    public void remove(){
      if(inicio==null|refAnt==null) throw new IllegalStateException();
      cntElem--;
      if(inicio==fim){
        inicio=fim=refAnt=null;
        return;
      }
      if(refAnt==inicio){
        inicio=inicio.prox;
        refAnt=null;
        return;
      }
      Cnodo a;
      for(a=inicio; a.prox!=refAnt; a=a.prox);
      a.prox=a.prox.prox;
      if(refAnt==fim){
        fim=a;
      }
      refAnt=null;
    }
}
class Cnodo{int info; Cnodo prox;}
private Cnodo inicio=null;
private Cnodo fim=null;
private int cntElem=0;

public boolean adicione(int i){
    Cnodo n=new Cnodo();
    n.info=i;
    n.prox=null;
    if(inicio==null){
      inicio=fim=n;
    }else{
      fim.prox=n;
      fim=n;
    }
    cntElem++;
    return true;
}
public void limpa(){
    cntElem=0;
    inicio=fim=null;
}
public boolean estaVazia(){
    return cntElem==0;
}
public int tamanho(){
    return cntElem;
}
public Iiterador iterador(){
    return new IteradorLE();
}
}

class sesnp{
public static void main(String[] arg){
    /* cria colecao de inteiros referida por nd /
    Icolecao nd = new ListaEncadeada();
    nd.adicione(123);
    nd.adicione(456);
   nd.adicione(789);
    nd.adicione(147);
    System.out.println("adicionou "+nd.tamanho()+" valores inteiros");
    for(;nd.tamanho()>0;){
      Iiterador it=nd.iterador();
      for(;it.temProximo();){
        System.out.println(it.proximo());
      }
      it.remove(); /* remove inteiro retornado por proximo() */
      System.out.println("removeu ultimo. Tem "+nd.tamanho()+" valores inteiros");
    }
}
}

A implementação acima utiliza uma técnica conhecida como encadeamento de nodos. Observe a figura abaixo.

Esta figura mostra uma coleção, implementada com encadeamento de nodos, em três diferentes instantes. No primeiro instante a coleção se encontra vazia. No segundo instante a coleção tem um elemento (o valor inteiro 123) e no terceiro instante foi adicionado o valor inteiro 456 à coleção.

O programa abaixo mostra uma outra implementação das interfaces Icolecao e Iiterador, desta vez uma implementação similar à ArrayList ou a Vector.

import java.util.*;

interface Iiterador{

boolean temProximo();

int proximo();

void remove();

}

interface Icolecao{

boolean adicione(int i);

Iiterador iterador();

void limpa();

boolean estaVazia();

int tamanho();

}

class ListaArranjo implements Icolecao{

classIteradorLA implements Iiterador{

int curr=0;

int indRemove=-1;

public boolean temProximo(){

return curr<cntElem;

}

public int proximo(){

if(curr>=cntElem)throw new NoSuchElementException();

indRemove=curr;

return rep[curr++];

}

public void remove(){

if(indRemove<0)throw new IllegalStateException();

cntElem--;

curr--;

for(int i=indRemove; i<=cntElem; i++) rep[i]=rep[i+1];

indRemove=-1;

}

private int tamanho=100;

int[] rep=new int[tamanho];

int cntElem=0;

public boolean adicione(int i){

if(cntElem>=rep.length)throw new RuntimeException("arranjo estorou!");

rep[cntElem++]=i;

return true;

}

public void limpa(){

cntElem=0;

}

public boolean estaVazia(){

return cntElem==0;

}

public int tamanho(){

return cntElem;

}

public Iiterador iterador(){

return new IteradorLA();

}

class colecaoarray{

public static void main(String[] arg){

Icolecao nd = new ListaArranjo();

nd.adicione(123);

nd.adicione(456);

nd.adicione(789);

nd.adicione(147);

System.out.println("adicionou "+nd.tamanho()+" itens");

for(;nd.tamanho()>0;){

Iiterador it=nd.iterador();

System.out.println(it.proximo());

it.remove();

for(;it.temProximo();){

System.out.println(it.proximo());

}

System.out.println("removeu. Tem "+nd.tamanho()+" itens");

}

A implementação abaixo é similar à LinkedList, ou seja similar a uma implementação já mostrado acima. Mas observe o uso de “Nodos Postiços” (“dummy nodes”). Com o uso de nodos postiços o código para inserção e remoção de nodos fica um pouco mais simples. O uso de nodos postiços é um aspecto de pouca importância mas é uma técnica difundida.

Exercício:

1. Faça o desenho, conforme convenções da disciplina, da coleção vazia.

2. Faça o desenho, conforme convenções da disciplina, da coleção com um elemento.

3. Faça o desenho da coleção com dois elementos.

4. Faça o desenho da coleção com três elementos e com o iterador referenciado por it logo após sua criação.

import java.util.NoSuchElementException;

interface Iiterador{

boolean temProximo();

int proximo();

void remove();

}

interface Icolecao{

boolean adicione(int i);

Iiterador iterador();

void limpa();

boolean estaVazia();

int tamanho();

}

classListaEncadeadaNP implements Icolecao{

class IteradorLENP implements Iiterador{

Cnodo curr=inicio.prox;

Cnodo refAnt=null;

publicboolean temProximo(){

return curr!=fim;

}

public int proximo(){

if(curr==fim) throw new NoSuchElementException();

refAnt=curr; /* marca nodo que pode ser removido */

curr=curr.prox;

return refAnt.info;

}

public void remove(){

if(refAnt==null) throw new IllegalStateException();

cntElem--;

Cnodo a;

for(a=inicio; a.prox!=refAnt; a=a.prox);

a.prox=a.prox.prox;

refAnt=null;

}

class Cnodo{int info; Cnodo prox;}

private Cnodo inicio;

private Cnodo fim;

private int cntElem;

ListaEncadeadaNP(){

inicio=new Cnodo();

fim=new Cnodo();

inicio.prox=fim;

fim.prox=null;

cntElem=0;

}

public boolean adicione(int i){

Cnodo n=new Cnodo();

n.info=i;

n.prox=inicio.prox;

inicio.prox=n;

cntElem++;

return true;

}

public void limpa(){

cntElem=0;

inicio.prox=fim;

}

public boolean estaVazia(){

return cntElem==0;

}

public int tamanho(){

return cntElem;

}

public Iiterador iterador(){

return new IteradorLENP();

}

class senp{

public static void main(String[] arg){

Icolecao nd = new ListaEncadeadaNP();

nd.adicione(123);

nd.adicione(456);

nd.adicione(789);

nd.adicione(147);

System.out.println("adicionou "+nd.tamanho()+" itens");

for(;nd.tamanho()>0;){

Iiterador it=nd.iterador();

for(;it.temProximo();){

System.out.println(it.proximo());

}

it.remove();

System.out.println("removeu ultimo. Tem "+nd.tamanho()+" itens");

}

A implementação abaixo utiliza o encadeamento duplo. A classe LinkedList na verdade usa é o encadeamento duplo! Além do encademento duplo é utilizado um nodo postiço e é feito um encadeamento “circular”.

import java.util.NoSuchElementException;

interface Iiterador{

boolean temProximo();

int proximo();

void remove();

}

interface Icolecao{

boolean adicione(int i);

Iiterador iterador();

void limpa();

boolean estaVazia();

int tamanho();

}

class ListaEncadeadaDE implements Icolecao{

class IteradorLDE implements Iiterador{

Cnodo curr=extr.prox;

Cnodo refAnt=null;

publicboolean temProximo(){

return curr!=extr;

}

public int proximo(){

if(curr==extr) throw new NoSuchElementException();

refAnt=curr;

curr=curr.prox;

return refAnt.info;

}

public void remove(){

if(refAnt==null) throw new NoSuchElementException();

cntElem--;

refAnt.prox.ant=refAnt.ant;

refAnt.ant.prox=refAnt.prox;

refAnt=null;

}

class Cnodo{int info; Cnodo ant; Cnodo prox;}

private Cnodo extr;

private int cntElem=0;

ListaEncadeadaDE(){

Cnodo nodoPostico=new Cnodo();

nodoPostico.ant=nodoPostico;

nodoPostico.prox=nodoPostico;

extr=nodoPostico;

}

public boolean adicione(int i){

cntElem++;

Cnodo n=new Cnodo();

n.info=i;

n.ant=extr;

n.prox=extr.prox;

extr.prox.ant=n;

extr.prox=n;

return true;

}

public void limpa(){

cntElem=0;

extr.ant=extr;

extr.prox=extr;

}

public boolean estaVazia(){

return cntElem==0;

}

public int tamanho(){

return cntElem;

}

public Iiterador iterador(){

return new IteradorLDE();

}

class denp{

public static void main(String[] arg){

Icolecao nd = new ListaEncadeadaDE();

nd.adicione(123);

nd.adicione(456);

nd.adicione(789);

nd.adicione(147);

System.out.println("adicionou "+nd.tamanho()+" itens");

for(;nd.tamanho()>0;){

Iiterador it=nd.iterador();

for(;it.temProximo();){

System.out.println(it.proximo());

}

it.remove();

System.out.println("removeu ultimo. Tem "+nd.tamanho()+" itens");

}

Universidade Federal de Minas Gerais Instituto de Ciências Exatas Departamento de Ciência da Computação

Coleções e iteradores

Universidade Federal de Minas Gerais
Instituto de Ciências Exatas
Departamento de Ciência da Computação