Si consideri la seguente classe astratta che specifica IL tipo di dato astratto “Lista circolare polimorfa omogenea”



Scaricare 38.5 Kb.
13.11.2018
Dimensione del file38.5 Kb.

Metodologie di Programmazione

30 Maggio 2005

Si consideri la seguente classe astratta che specifica il tipo di dato astratto “Lista circolare polimorfa omogenea”. Circolare vuol dire che, se la lista ha n elementi, l’ultimo elemento ha come successore il primo.
public abstract class Clist {

// OVERVIEW: una Clist è una lista circolare omogenea non modificabile

// di Objects. Elemento tipico [x1,...,xn,x1,...,xn, ….]

public abstract Object first () throws EmptyException;



// EFFECTS: se this è vuoto solleva EmptyException, altrimenti

// ritorna il primo elemento di this

public abstract boolean isempty ();



// EFFECTS: se this è vuota ritorna true, altrimenti ritorna false

public abstract Clist rest () throws EmptyException;



// EFFECTS: se this è vuoto solleva EmptyException, altrimenti

// ritorna la lista ciclica ottenuta da this togliendo il primo

// elemento

public abstract Iterator elements ();



// EFFECTS: ritorna un generatore che produrrà tutti gli elementi di

// this (come Objects) nell’ordine che hanno in this

public abstract Clist insert (Object x) throws NullPointerException ClassCastException;



// EFFECTS: se x e’ null solleva NullPointerexception, se x non è dello stesso tipo degli elementi contenuti in

// this, solleva ClassCastException, altrimenti restituisce la lista

// ottenuta aggiungendo x all’inizio di this

public abstract Clist remove (Object x);



// EFFECTS: restituisce la lista ottenuta rimuovendo x da this

public abstract Clist ruotadiuno () throws EmptyException;



// EFFECTS: se this è vuoto solleva EmptyException, altrimenti

// ritorna la lista ciclica ottenuta da this spostando avanti di uno

// il primo elemento. Tipo: se this=[x1,...,xn,x1,...,xn, ….] allora

// restituisce [xn,x1,...,xn-1,xn,x1,...,xn-1, ….]

}

Si definisca una implementazione gerarchica con due sottoclassi concrete che realizzano il caso lista vuota e quello lista non vuota, eseguendo quanto richiesto nel seguito:




  1. Per ciascuna delle due classi, si forniscano la rappresentazione, la funzione di astrazione e l’invariante di rappresentazione, e si mostrino le implementazioni dei costruttori.

Sottotipo EmptyClist non ha variabili d’istanza e quindi neanche invariante.


Funzione di astrazione: aEmptyClist(c) = []

Costruttore


public EmptyClist(){}

Sottotipo FullClist ha le seguenti variabili d’istanza

private Object val; //il valore

private FullClist next;// il resto della lista

private boolean ultimo;//indica se e’ l’ultimo

Funzione di astrazione:

aFullClist(c) = [c.val] …… se c.ultimo

altrimenti


aFullClist(c) = [c.val] + [x1,….,xn] + [c.val] + [x1,….,xn]+ …. se aFullClist(c.next)=[x1,….,xn]

In variante: IFullClist (c)= c.val!=null e c.ultimo oppure


c.next!=null e c.val!=null e IFullClist (c.next) e

c.val.getClass()=c.next.val.getClass()

Costruttore: public FullClist(Object o){if (o==null) throw

new NullPointerException(“FullClist”);

val=o; ultimo=true;}





  1. Per la classe che realizza il caso non vuoto,

    1. Si fornisca l’implementazione del metodo elements.

public Iterator elements (){



// EFFECTS: ritorna un generatore che produrrà tutti gli elementi di

// this (come Objects) nell’ordine che hanno in this

return ClistGen(this);}


Classe Interna che definisce il generatore

private static class ClistGen implements {
private FullClist io; \\la lista completa su cui deve iterare

private FullClist current; \\il nodo della lista dove siamo arrivati


public ClistGen(FullClist l) {io=l; current=io;}
public boolean hasNext() {return true;}
public Object next()throws NoSuchElementException{

Object el=current.val;

if (current.ultimo) {current=io;}

else current=current.next;

return el;}

}



    1. Si fornisca l’implementazione dei metodi insert e ruotadiuno.

public abstract Clist insert (Object x) throws NullPointerException ClassCastException;



// EFFECTS: se x e’ null solleva NullPointerexception, se x non è dello stesso tipo degli elementi contenuti in

// this, solleva ClassCastException, altrimenti restituisce la lista

// ottenuta aggiungendo x all’inizio di this

if (x==null) throw new NullPointerException(“insert”);

Class tipo=val.getClass();

if (! tipo.isinstance(x)) throws new ClassCastException(“insert”);

FullClist n=new FullClist(x);

n.next=this;

n.ultimo=false;

return n;}

public abstract Clist ruotadiuno () throws EmptyException;

// EFFECTS: se this è vuoto solleva EmptyException, altrimenti

// ritorna la lista ciclica ottenuta da this spostando avanti di uno

// il primo elemento. Tipo: se this=[x1,...,xn,x1,...,xn, ….] allora

// restituisce [xn,x1,...,xn-1,xn,x1,...,xn-1, ….]

if (ultimo) return new FullClist(val);

FullClist l= (FullClist) next.ruotadiuno(); //chiamata ricorsiva fa //scorrere il resto

FullClist n=new FullClist(l.val);

l.val=val;

n.next=l;

n.ultimo=false;

return n;}



    1. Si dimostri che l’implementazione del metodo insert preserva l’invariante di rappresentazione e soddisfa la propria specifica.



Il metodo soddisfa l’invariante perche’ esegue icontrolli sul tipo e fa in modo che il next sia inizializzato.


Condividi con i tuoi amici:


©astratto.info 2019
invia messaggio

    Pagina principale