Si consideri la classe astratta che specifica IL tipo di dato astratto Tabella



Scaricare 48.69 Kb.
17.11.2017
Dimensione del file48.69 Kb.


Albero binario etichettato

Si consideri la seguente classe astratta che specifica il tipo di dato astratto “Albero binario etichettato”. Un albero binario è un albero in cui ogni nodo o è una foglia oppure ha esattamente due sottoalberi (sinistro e destro). Le etichette delle foglie sono valori sommabili (Addable).

public abstract class BESalbero {

// OVERVIEW: Un BESalbero è un

// albero binario, in cui nodi

// e foglie sono etichettati con

// valori omogenei sommabili.

// L’etichetta di un nodo è la

// somma delle etichette dei due // suoi sottoalberi.

// Un BESalbero è modificabile

// Tipici valori astratti: n

// se è una foglia etichettata n

// (n, a1, a2) , se è un nodo

// etichettato n con sottoalberi // a1 ed a2

public abstract BESalbero sinistro () throws NotANode;



// EFFECTS: se this è una foglia // solleva NotANode, altrimenti

// ritorna il sottoalbero

// sinistro di this

public abstract BESalbero

destro () throws NotANode;

// EFFECTS: se this è una foglia // solleva NotANode, altrimenti

// ritorna il sottoalbero destro // di this

public abstract Addable

etichetta ();

// EFFECTS: ritorna l’etichetta

// di this

public abstract boolean foglia();



// EFFECTS: se this è una foglia

// ritorna true, altrimenti

// ritorna false

public abstract BESalbero

nuovoalbero (BESalbero d)

throws ClassCastException,

NullPointerException;

// EFFECTS: se d e’ null solleva // NullPointerException;

// se le etichette di d non hanno

// lo stesso tipo delle etichette // di this, solleva

// ClassCastException; altrimenti

// restituisce un nuovoBESalbero,

// i cui sottoalberi sinistro e

// destro sono this e d.

public abstract void

rimpiazzasinistro (BESalbero s)

throws ClassCastException,

NullPointerException, NotANode;

// MODIFIES:this

// EFFECTS: se s è null solleva

// NullPointerException;

// se this è una foglia solleva

// NotANode, se il tipo delle

// etichette di s è diverso da

// quello delle etichette di this

// solleva ClassCastException,

// altrimenti rimpiazza il

// sottoalbero sinistro di this // con s.

}

Si definisca una implementazione gerarchica con due sottoclassi concrete che realizzano i casi foglia e nodo, eseguendo quanto richiesto nel seguito:





  1. Per ciascuna delle due sottoclassi, si forniscano

a. la specifica con eventuali dimostrazioni di validità della regola dei metodi.

SPECIFICA DI FOGLIA

public class Foglia extends

BESalbero {

// OVERVIEW: Una foglia è

// etichettata con un valore di

// tipo Addable. E` modificabile.
public Foglia (Addable a) throws

NullPointerException{

// EFFECTS: se a è null solleva

// NullPointerException,

// altrimenti costruisce la

// foglia con etichetta a}


public BESalbero sinistro ()

throws NotANode{

// EFFECTS: solleva NotANode}
public BESalbero destro ()

throws NotANode{

// EFFECTS: solleva NotANode}

public Addable etichetta (){

// EFFECTS:uguale}
public boolean foglia(){

// EFFECTS ritorna true}

public BESalbero nuovoalbero

(BESalbero d) throws

ClassCastException,

NullPointerException{

// EFFECTS: uguale}.
public void rimpiazzasinistro

(BESalbero s)throws

ClassCastException,

NullPointerException, NotANode{

// MODIFIES:this

// EFFECTS: solleva NotANode}

}

SPECIFICA DI NODO


public class Nodo extends

BESalbero {

// OVERVIEW: Un Nodo è un albero

// binario, con etichetta che e’

// la somma dei valori (Addable)

// del sottoalbero sinistro e

// destro. E` modificabile.

// Tipici valori astratti:

// (n, a1, a2) , se è un nodo

// etichettato n con sottoalberi

// a1 ed a2
public Nodo (BESalbero s,

BESalbero d) throws

ClassCastException,

NullPointerException {

// EFFECTS: se s o d sono null

// solleva NullPointerException;

// se le etichette di d ed s non

// hanno lo stesso tipo

// solleva ClassCastException;

// altrimenti inizializza this

// al nodo i cui sottoalberi

// sinistro e destro sono s e d.


public BESalbero sinistro () {

// EFFECTS: ritorna il

// sottoalbero sinistro di this}
public BESalbero destro (){

// EFFECTS:ritorna il sottoalbero

// destro di this
public Addable etichetta (){

// EFFECTS: uguale


public boolean foglia(){

// EFFECTS: ritorna false}


public BESalbero nuovoalbero

(BESalbero d) throws

ClassCastException,

NullPointerException{

// EFFECTS: uguale}

public abstract void

rimpiazzasinistro (BESalbero s)

throws ClassCastException,

NullPointerException, NotANode{

// MODIFIES:this

// EFFECTS: se s è null solleva

// NullPointerException;

// se il tipo delle etichette di

// s è diverso da quello delle

// etichette di this solleva

// ClassCastException, altrimenti

// rimpiazza il sottoalbero

// sinistro di this con s.}

}
Il principio di sostituzione è soddisfatto da entrambi i sottotipi, che realizzano i due casi della definizione.

In entrambi i casi i metodi del sottotipo fanno esattamente quello che è richiesto dai metodi del supertipo.




  1. la rappresentazione, la funzione di astrazione e l’invariante di rappresentazione

c. l’implementazione del costruttore con dimostrazione che preserva l’invariante di rappresentazione.

FOGLIA
Rappresentazione:
private Addable label;
Funzione di astrazione:

alpha(c)=c.label


Invariante: I(c)= c.label!=null
public Foglia (Addable a) throws NullPointerexception{

// EFFECTS: se a è null solleva

// NullPointerException,

// altrimenti costruisce la

// foglia con etichetta a

if (a==null) throw new NullPointerexception(“Foglia”);

label=a; }

L’invariante e’ soddisfatto perché garantisce label!=null


NODO
Rappresentazione:


private Addable label;

private BESalbero sx;

private BESalbero dx;
Funzione di astrazione: alpha(c)=(c.label, alpha(c.sx),alpha(c.dx))
Invariante: I(c)=c.label!=null & c.sx!=null & c.dx!=null &

I(c.sx) & I(c.dx) &

c.label.getClass().

isinstance(c.sx.etichetta()) &

c.label.getClass().

isinstance(c.dx.etichetta()) &

c.label=c.sx.etichetta().

add(c.dx.etichetta())

public Nodo (BESalbero s,

BESalbero d)

throws NullPointerException,

classCastException {

// EFFECTS: se s o d sono null

// solleva NullPointerException;

// se le etichette di d ed s

// non hanno lo stesso tipo

// solleva ClassCastException;

// altrimenti inizializza this al

// nodo i cui sottoalberi

// sinistro e destro sono s e d.


if (s==null||d==null) throw new NullPointerexception(“Nodo”);

label=s.etichetta().

add(d.etichetta());

sx=s; dx=d;}


Il costruttore soddisfa l’invariante perché: s e d soddisfano l’invariante per ipotesi. E` garantito che che sx e dx non siano null. Label viene inizializzato con la somma delle radici di s e d; il metodo add dell’interfaccia Addable solleva ClassCastException se non sono omogenei.


  1. Per la classe che realizza il caso nodo,si fornisca l’implementazione dei metodi nuovoalbero e rimpiazzasinistro.

public BESalbero nuovoalbero (BESalbero d) throws ClassCastException, NullPointerException{

// EFFECTS: uguale

return new Nodo(this,d);}

public abstract void rimpiazzasinistro (BESalbero s)

throws ClassCastException, NullPointerException, NotANode{

// MODIFIES:this

// EFFECTS: se s è null solleva NullPointerException; se il tipo

// delle etichette di s è diverso

// da quello delle etichette di

// this solleva ClassCastException // altrimenti rimpiazza il

// sottoalbero sinistro di this con s.

if (s==null) throw new NullPointerexception(“Nodo.rs”);

Addablesum=label.sub(sx.etichetta());



sum=sum.add(s.etichetta());

sx=s; label=sum;}



©astratto.info 2017
invia messaggio

    Pagina principale