Ereditarietà e downcasting

MagoAntò

il 24 apr 2012, 15:04

13 risposte

MagoAntò

Pochi posts

Iscritto da: apr, 2011

Messaggi:: 20

Ereditarietà e downcasting

24 apr 2012, 15:29

Ciao a tutti!

Sto realizzando un programma in C++ per l'implementazione di un vocabolario mediante alberi Red Black. Nella traccia viene espressamente richiesto di fare uso dell'ereditarietà.

Ho strutturato il programma in questo modo:

    class nodo_BST
    {
    protected:
            string chiave;
            nodo_BST *sx;
            nodo_BST *dx;
            nodo_BST *padre;
     
    public:
            nodo_BST() // Costruttore
            {
                    chiave = "";
                    sx = NULL;
                    dx = NULL;
                    padre = NULL;
     
            }
           
            ~nodo_BST() // Distruttore
            {
            }
     
            string get_chiave()
            {
                    return chiave;
            }
           
            void set_chiave(string c)
            {
                    chiave = c;
            }
           
            nodo_BST* get_sx()
            {
                    return sx;
            }
           
            void set_sx(nodo_BST *sinistra)
            {
                    sx = sinistra;
            }
           
            nodo_BST* get_dx()
            {
                    return dx;
            }
           
            void set_dx(nodo_BST *destra)
            {
                    dx = destra;
            }
           
            nodo_BST* get_padre()
            {
                    return padre;
            }
           
            void set_padre(nodo_BST *p)
            {
                    padre = p;
            }
    };
     
    class nodo_RB : public nodo_BST
    {
    private:
            colore c;
     
    public:
            nodo_RB():nodo_BST() // invoco il costruttore della superclasse
            {
                    c = nero;
            }
           
            ~nodo_RB()
            {
     
            }
     
            colore get_color ()
            {
                    return c;
            }
     
     
            void set_color (colore colore_in)
            {
     
                    c = colore_in;
            }
    };

Come potete vedere, la classe nodo_RB è una sottoclasse di nodo_BST. Il problema è il seguente: mettiamo caso che, per esempio, dopo aver creato un oggetto della classe nodo_RB, debba necessariamente invocare il metodo get_sx per conoscere il figlio sinistro del nodo corrente. Il compilatore mi da errore, dicendo che il metodo della superclasse restituisce un nodo_BST.

Come risolvere il problema?

Ho letto che può essere utilizzato il downcasting (magari quello dinamico che controlla pure se il tipo "castato" è effettivamente diventato quello richiesto) ma mi chiedevo se fosse possibile prendere un'altra strada.

Grazie in anticipo per le risposte!

13 Risposte

B
barba59
Molto attivo
Iscritto da
feb, 2012
Messaggi:
1353
Re: Ereditarietà e downcasting
24 apr 2012, 17:37
Ciao MagoAntò,
si usa l' ereditarieta pubblica quando quando la relazione tra le classi può essere espressa con la relazione E'-UN, se invece vale la relazione (come nel tuo caso) E'-IMPLEMENTATO-IN-TERMINI_DI bisogna usare l' ereditarietà non pubblica (o meglio ancora il contenimento).

Se la classe nodo_RB deriva in maniera protetta da nodo_BST non puoi scrivere nodo_BST* b = new nodo_RB();
```
class nodo_RB: protected nodo_BST 
{
   ...
};

nodo_BST* b = new nodo_RB();  // errore
```
A questo punto la classe derivata rimappa le funzioni della class base controllandone il tipo:
```
    void nodo_RB::set_dx(nodo_RB *destra)
    {
         nodo_BST::set_dx(destra);
    }

    nodo_RB* nodo_RB::get_dx()
    {
         return (nodo_RB*) nodo_BST::get_dx();
    }
```
In pratica la classe derivata sfrutta l' implementazione della classe base derivando in maniera protetta e impone che la costruzione dell' albero avvenga solo attraverso oggetti 'nodo_RB'.
```
    nodo_RB* root = new nodo_RB();
    root->set_dx(new nodo_RB());
    nodo_RB* child = root->get_dx();

    ...
    root->set_dx(new nodo_BST()); // sbagliato, errore di compilazione
    
```
Spero di aver reso un poco l' idea, per approfondimenti puoi vedere 'Exceptional C++' di Herb Sutter.
M
MagoAntò
Pochi posts
Iscritto da
apr, 2011
Messaggi:
20
Re: Ereditarietà e downcasting
24 apr 2012, 19:07
Grazie mille per l'aiuto, sei stato estremamente gentile!
Quindi, scusa se mi ripeto, se nella classe nodo_BST ho questi tre metodi (solo le firme, le implementazioni sono in un file .cpp a parte):
```
void inserisci_nodo(nodo_BST **root, string key);
nodo_BST* ricerca_termine (nodo_BST *root, string key);
void visita_inorder (nodo_BST *nodo);
```
devo ricopiarli nella classe nodo_RB e cambiarli così?
```
void inserisci_nodo(nodo_RB **root, string key);
nodo_BST* ricerca_termine (nodo_RB *root, string key);
void visita_inorder (nodo_RB *nodo);
```
E le implementazioni? Non mi troverei poi, nel file .cpp, con due metodi con lo stesso corpo se non per il tipo di nodo diverso?
B
barba59
Molto attivo
Iscritto da
feb, 2012
Messaggi:
1353
Re: Ereditarietà e downcasting
24 apr 2012, 19:33
Ciao MagoAntò,
se quei metodi devono essere pubblici si, devi ridefinirli come hai scritto, se sono protetti no, non è necessario. In pratica la classe nodo_RB deve esporre solo metodi che trattano nodo_RB, internamente può usare il nodo antenato.

La funzione che ridefinisci è solo una shell verso il metodo originale, non devi copiare il codice, devi solo convertire i tipi, ad esempio:
```
nodo_RB* nodo_RB::ricerca_termine(nodo_RB* root, string key)  // attenzione qui avevi scritto un tipo di ritorno sbagliato
{
    return (nodo_RB*) nodo_BST::ricerca_termine(root, key);
}
```
Non ho idea quali di quei tre metodi devono essere pubblici e quali protetti, vedi un po tu (rendi pubblico solo lo stretto necessario).
Buon lavoro.
M
MagoAntò
Pochi posts
Iscritto da
apr, 2011
Messaggi:
20
Re: Ereditarietà e downcasting
24 apr 2012, 20:14
Sono tutti e tre metodi pubblici, quindi devo modificare la firma cambiando opportunamente i nodi_BST con nodi_RB e aggiungere il "rimando" ai metodi della superclasse, se ho ben capito.
Ho un dubbio solo su uno dei metodi void: il compilatore continua a dirmi 'inserisci_nodo' : cannot convert parameter 1 from 'class nodo_RB ** ' to 'class nodo_BST ** ' Types pointed to are unrelated; conversion requires reinterpret_cast, C-style cast or function-style cast
L'istruzione che genera l'errore è
```
void nodo_RB :: inserisci_nodo(nodo_RB **root, string key)
{
	nodo_BST :: inserisci_nodo(root, key);
}
```
Continuo a provare! Grazie ancora.
B
barba59
Molto attivo
Iscritto da
feb, 2012
Messaggi:
1353
Re: Ereditarietà e downcasting
24 apr 2012, 20:35
È giusto nodo_RB **root oppure è una svista ed è nodo_RB *root (un solo asterisco)?

MagoAntò

Pochi posts

Iscritto da: apr, 2011

Messaggi:: 20

Re: Ereditarietà e downcasting

25 apr 2012, 00:37

Si, è proprio un puntatore a puntatore.

Questa è l'implementazione del metodo nella classe padre:

void nodo_BST :: inserisci_nodo(nodo_BST **root, string key)
{
	nodo_BST *x, *y, *z;
	bool empty = false;

        z = new nodo_BST;
	z->set_chiave(key);
	y = NULL;
	
	x = *root; // punta alla radice

	// Ricerca posizione del nuovo nodo

	while (x != NULL) // Se l'albero non è vuoto..
	{
		y = x; // y punta alla posizione del nodo corrente

		if (z->get_chiave()<x->get_chiave())
		{
			x = x->get_sx(); // scendo a sinistra
		}
		else
		{
			x = x->get_dx();
		}
	}

	z->set_padre(y);

	if (y == NULL)
	{
		empty = true;
		*root = z; // CASO II
	}

	// CASO I

	else if (z->get_chiave()<y->get_chiave())
	{
		y->set_sx(z);
	}
	else
	{
		y->set_dx(z);
	}

	z->set_sx(NULL);
	z->set_dx(NULL);
	
	if (empty == true)
	{
		*root = z;
	}
}

B
barba59
Molto attivo
Iscritto da
feb, 2012
Messaggi:
1353
Re: Ereditarietà e downcasting
25 apr 2012, 08:54
Ciao MagoAntò,
tieni presente che non conosco il problema che devi risolvere, quindi non vorrei insistere su una strada che magari è sbagliata. Tutto il ragionamento è partito supponendo che tra i nodi esistesse la relazione 'è-implementato-in-termini-di', ma magari non è cosi.

La classe nodo_BST è una classe che devi riutilizzare e non puoi modificare o è una classe che hai scritto tu e puoi modellare come ti pare?
Ad esempio il metodo 'inserisci_nodo' crea un oggetto di tipo nodo_BST, e questo ti impedisce di creare alberi di nodi_RB. Potrebbe essere fatto in modo diverso, ma questo dipende da che specifiche hai ricevuto.
M
MagoAntò
Pochi posts
Iscritto da
apr, 2011
Messaggi:
20
Re: Ereditarietà e downcasting
25 apr 2012, 12:15
La traccia non mi obbliga a sviluppare le classi in un certo modo, ho libera scelta su quello, mi chiede solo di usare l'ereditarietà; da qui la mia idea, forse sbagliata nell'implementazione, di creare una classe base "albero binario" con tutti i suoi metodi e poi creare una sottoclasse "albero red black" che dovrebbe usare i metodi della superclasse.

Ti ringrazio ancora tantissimo per l'aiuto che mi stai dando.
B
barba59
Molto attivo
Iscritto da
feb, 2012
Messaggi:
1353
Re: Ereditarietà e downcasting
26 apr 2012, 13:25
Ciao MagoAntò
l' idea mi sembra giusta, prosegui tranquillo, ti do solo qualche suggerimento:

- Rendi pubblico solo quello che necessario, un vocabolario ha bisogno di usare delle intefacce del tipo InserisciParola(string), CercaParola(string) e non ne vuol sapere nulla del tipo dei nodi (l' implementazione deve essere nascosta).

- Tutto sommato credo ti convenga partire da una classe Vocabolario, definirne le intefaccie, e poi basare la sua implementazione si un albero RB, ovvero la classe Vocabolario contiene un nodo RB radice e ne chiama i metodi.

- Se la classe nodo BST è pensata per essere estesa è bene che il suo metodo inserisci_nodo non crei dei nodi. Potresti cambiare la sua interfaccia per ricevere il nodo già creato, oppure potrebbe crearlo ma richiamando un metodo virtuale che la classe derivata ridefinisce.

Mi rendo conto che a questo punto ci stiamo allontanando da quello che era l' argomento di questo topic, ti saluto e ti auguro buon lavoro.
M
MagoAntò
Pochi posts
Iscritto da
apr, 2011
Messaggi:
20
Re: Ereditarietà e downcasting
26 apr 2012, 19:38
Sono riuscito a sbloccare la situazione cambiando la firma del metodo inserisci_nodo: come mi hai suggerito, in input non passo più il nodo ma solo la stringa. Il nodo RB viene creato grazie ad una funzione apposita richiamata dall'interno del corpo di inserisci_nodo. Starò anche attento alle interfacce, rendendo pubblico solo ciò che serve.

Grazie mille, mi sei stato di grandissimo aiuto!
M
MagoAntò
Pochi posts
Iscritto da
apr, 2011
Messaggi:
20
Re: Ereditarietà e downcasting
01 mag 2012, 16:57
Mi permetto di continuare la discussione: ho completato l'intero programma, ma mi era venuta in mente un'altra soluzione per evitare quei cast, ovvero, l'uso dei template. In questo caso particolare caso, però, conviene usarli? Dovrei comunque sfruttare l'ereditarietà, come viene richiesto nelle specifiche.
B
barba59
Molto attivo
Iscritto da
feb, 2012
Messaggi:
1353
Re: Ereditarietà e downcasting
02 mag 2012, 13:38
Ciao MagoAntò,
l' uso del downcasting può essere indice di una cattiva organizzazione delle classi, ma non necessariamente è sempre così, in alcuni casi è giustificato.

Dico questo per ricordarti che il tuo problema principale non era evitare i cast, ma fare un dizionario basato sui nodi RB che in qualche modo usasse l' ereditarietà. E da quello che dici mi sembra che hai raggiunto l' obiettivo. Per cui alla tua

Provare ad usare i template potrebbe essere interessante ma probabilmente ti conviene farlo su un altro progetto.
M
MagoAntò
Pochi posts
Iscritto da
apr, 2011
Messaggi:
20
Re: Ereditarietà e downcasting
02 mag 2012, 19:02
Ciao barba59,

si, alla fine ce l'ho fatta! (grazie anche al tuo supporto! )

L'idea di utilizzare i template mi è venuta in mente dopo quella del dynamic casting. Vorrei usare questo tipo di casting perchè, almeno, esegue un controllo sulla variabile castata, ma non ci sono riuscito. Non volendo tirarla troppo per le lunghe:
```
class nodo_BST // Nodo di un albero binario
{
private:
	...
	nodo_BST *padre;

public:
	...
	nodo_BST* get_padre()
	{
		return padre;
	}

	virtual void dummy () // dichiarato perchè il dynamic cast funziona solo con classi polimorfiche
	{
	}
};

class nodo_RB : public nodo_BST
{
private:
	colore c;
	nodo_RB* temp;

public:
	...
	nodo_RB* get_padre()
	{
		temp = dynamic_cast<nodo_RB*>(nodo_BST::get_padre());
		
		if (temp)
		{
			cout<<"Conversione riuscita!"<<endl;
			return temp;
		}
		else
			cout<<"Fallimento"<<endl;
	}
};
```
Purtroppo temp viene settato a NULL ed il programma non può continuare. Beh, male che vada non uso il casting dinamico e lascio tutto così com'è.

Grazie ancora!

Devi accedere o registrarti per scrivere nel forum

13 risposte