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



Scaricare 31.5 Kb.
13.12.2017
Dimensione del file31.5 Kb.

Lista circolare

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 è 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] + [c.val]+ …… se c.ultimo

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

Invariante:


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 è null

// solleva

// NullPointerexception,

//se x non è dello stesso

// tipo degli elementi

// contenuti in this, solleva

// ClassCastException,

// se no 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 perché esegue i controlli sul tipo e fa in modo che il next sia inizializzato.


Condividi con i tuoi amici:


©astratto.info 2019
invia messaggio

    Pagina principale