[JAVA] Implementazione albero

[VincenzoTheBest]

Salve ragazzi,

sto cercando di implementare in java il dato astratto Albero.

La sua interfaccia è la seguente:

public interface Albero
{
	public boolean alberoVuoto();
	public Nodo radice();
	public Nodo padre(Nodo figlio);	
	public Nodo primoFiglio(Nodo padre);
	public Nodo succFratello(Nodo f);
	public void insprimoSottoAlbero(Nodo padre, Albero a);
	public void insSottoAlbero(Nodo fratello, Albero a);
	public void insRadice(Object info);
	public void cambiaInfo(Nodo n, Object info);
	public Object info(Nodo n);
	public void cancSottoAlbero(Nodo n);
	public boolean foglia(Nodo n);
	public boolean fineFratelli(Nodo n);
}

Per quanto riguarda gli operatori insprimoSottoAlbero e insSottoAlbero:
il primo rende la radice del sottoalbero primo figlio del nodo specificato (dell'albero corrente in cui lo si sta inserendo),
mentre il secondo operatore rende la radice del sottoalbero fratello del nodo specificato.

La classe che implementa l'interfaccia è la seguente:

package treeVettorePadri;

import tree.*;
import Eccezioni.*;
import java.util.Iterator;
import java.util.LinkedList;

public class AlberoVP implements Albero, Iterable {

	private NodoVP[] padri = new NodoVP[0];
	private NodoVP[] nodi = new NodoVP[0];
	
	
	public boolean alberoVuoto() 
	{
		return nodi.length == 0;
	}

	private boolean checkNode(Nodo v) 
	{
		if (v == null)
			return true;
		
		// per verificare che il nodo passato appartiene proprio all'albero this
		if (((NodoVP) v).albero != this)
			return true;
		
		return false;
	}
	
	
	public Nodo padre(Nodo v) 
	{
		if (checkNode(v))
			throw new EccezioneNodoInvalido();
		
		return padri[((NodoVP) v).indice];
	}
	
	
	public Nodo primoFiglio(Nodo v) throws EccezioneNodoInvalido
	{
		if (checkNode(v))
			throw new EccezioneNodoInvalido();
		
		for (int i=((NodoVP)v).indice+1; i<padri.length; i++)
			if (padri[i] == v)
				return nodi[i];
		throw new RuntimeException();
	}
	
	public boolean foglia(Nodo v) throws EccezioneNodoInvalido
	{
		if (checkNode(v))
			throw new EccezioneNodoInvalido();
		
		for (int i = ((NodoVP)v).indice+1; i < padri.length; i++)
			if (padri[i] == v)
				return false;
		
		return true;
	}
	
	
	public Nodo radice() throws AlberoVuotoException
	{	
		if(alberoVuoto())
			throw new AlberoVuotoException("Albero vuoto");
		
		return nodi[0];
	}


	public void insRadice(Object info) throws EccezioneNodoEsistente
	{
		if(!alberoVuoto())
			throw new EccezioneNodoEsistente();
		
		padri = new NodoVP[1];
		padri[0] = null;
		
		nodi = new NodoVP[1];
		nodi[0] = new NodoVP(info);
		nodi[0].albero=this;
	}


	public Object info(Nodo v) throws EccezioneNodoInvalido
	{
		if (checkNode(v))
			throw new EccezioneNodoInvalido();
		
		return nodi[((NodoVP) v).indice].info;
	}
	

	public void cambiaInfo(Nodo v, Object info) throws EccezioneNodoInvalido
	{
		if (checkNode(v))
			throw new EccezioneNodoInvalido();
		
		((NodoVP) v).info = info;
	}

	
	/*
	 * fratello è il nodo accanto a cui innestiamo il nuovo albero a
	 * (la radice dell'albero a diventa fratello del parametro fratello)
	 */
	public void insSottoAlbero(Nodo fratello, Albero a) throws EccezioneNodoInvalido
	{
		if (checkNode(fratello))
			throw new EccezioneNodoInvalido();

		int indice=((NodoVP)fratello).indice;
		
		//array di supporto per ampliare l'albero corrente
		NodoVP[] tmpNodi= new NodoVP[nodi.length + ((AlberoVP)a).nodi.length];
		NodoVP[] tmpPadri= new NodoVP[padri.length + ((AlberoVP)a).padri.length];
		
		System.arraycopy(nodi, 0, tmpNodi, 0, indice+1); // copio fino a fratello
		System.arraycopy(padri, 0, tmpPadri, 0, indice+1);
		
		//innesto l'albero a
		tmpNodi[indice+1]=(NodoVP)((AlberoVP)a).radice();
		tmpNodi[indice+1].albero=this;
		tmpNodi[indice+1].indice=indice+1; //nuovo indice radice di a
		
		tmpPadri[indice+1]= (NodoVP) padre(fratello); // assegno il padre (che è dunque lo stesso di fratello)
		
		//copia il resto dei nodi (da fratello in poi), spostandoli in avanti
		//copia il resto dei padri
		for(int i=indice+1; i<nodi.length; i++) 
		{
			tmpNodi[i+1] = nodi[i];
			tmpNodi[i+1].indice = i+1;
			tmpPadri[i+1] = padri[i];
		}
		
		int j=1; //innesto 
		for(int i=nodi.length+1; i<=tmpNodi.length-1; i++) // aggiungo i figli della radice di a
		{
			tmpNodi[i] = ((AlberoVP)a).nodi[j];
			tmpNodi[i].indice = i;
			tmpNodi[i].albero=this;
			tmpPadri[i] = ((AlberoVP)a).padri[j];
			j++;
		}
	
		padri=tmpPadri;
		nodi=tmpNodi;
	}

	private void rimuoviNodo(NodoVP u) 
	{
		int n = padri.length;

		NodoVP[] temp = new NodoVP[n - 1];
		//Cancellare elemento in posizione u.indice di nodi e ricompattare
		System.arraycopy(nodi, 0, temp, 0, u.indice);
		System.arraycopy(nodi, u.indice+1, temp, u.indice, temp.length-u.indice);
		nodi = temp;

		temp = new NodoVP[n - 1];
		System.arraycopy(padri, 0, temp, 0, u.indice);
		System.arraycopy(padri, u.indice+1, temp, u.indice, temp.length- u.indice);
		padri = temp;
		
		for (int i = 0; i < nodi.length; i++)
			nodi[i].indice = i;
	}

	
	public void cancSottoAlbero(Nodo v) throws EccezioneNodoInvalido
	{
		if (checkNode(v))
			throw new EccezioneNodoInvalido();
		
		Nodo temp;
		
		if (!foglia(v)) 
		{
			temp = primoFiglio(v);
			LinkedList<NodoVP> listFratelli=new LinkedList<NodoVP>(); 
			listFratelli.add((NodoVP)temp);
			
			while(!fineFratelli(temp))
			{
				temp = succFratello(temp);
				listFratelli.add((NodoVP)temp);
			}
			
			Iterator<NodoVP> it=listFratelli.iterator();
			
			while(it.hasNext())
			{
				temp=it.next();
				cancSottoAlbero(temp);
			}
			
		}
		
		rimuoviNodo((NodoVP) v);
	}

	
	public Iterator iterator() 
	{
		return new TreeIterator(this);
	}


	public String toString()
	{
         //...
	}
	
	private String toString(Nodo u)
	{
          //...
	}
	
	
	public boolean fineFratelli(Nodo v) throws EccezioneNodoInvalido
	{
           //...
	}


	/*
	 * Innestiamo l'albero a come primofiglio del nodo u
	 */
	public void insprimoSottoAlbero(Nodo u, Albero a) throws EccezioneNodoInvalido
	{
		if(checkNode(u))
			throw new EccezioneNodoInvalido();
		
		//array di supporto per ampliare l'albero corrente
		NodoVP[] tmpNodi= new NodoVP[nodi.length + ((AlberoVP)a).nodi.length];
		NodoVP[] tmpPadri= new NodoVP[padri.length + ((AlberoVP)a).padri.length];
		
               //...	
	}


	public Nodo succFratello(Nodo v) throws  EccezioneNodoInvalido
	{
		//...
	}

}

Vorrei capire come impostare l'operatore insprimoSottoAlbero(Nodo u, Albero a)?

E' diverso concettualmente dall'operatore insSottoAlbero (di cui dispongo già dell'implementazione)

[VincenzoTheBest]

Nessuno è disposto ad aiutarmi?