Iterare Albero ternario di ricerca

di
g.lombardo4
il
4 risposte
G
g.lombardo4
Pochi posts
Iscritto da
lug, 2020
Messaggi:
45

Iterare Albero ternario di ricerca

Salve a tutti programmatori,

ho creato un albero ternario e mi piacerebbe renderlo iterabile con un for.
Nello specifico all'interno dell'albero vengono inserite delle stringhe.
Seguendo una guida ho provato ad aggiungere quelle parti di codice per renderlo iterabile (in ordine, quindi prima nodo sx, poi centro e infine dx), ma cercando di iterare con un for tutti gli elementi dell'albero si presenta un errore:
Can only iterate over an array or an instance of java.lang.Iterable
.
Vi riporto qui di seguito il codice, così magari mi date una mano a capire cosa cambiare.
Grazie in anticipo.

Classe main 

package MAIN;

import ALBERO.Albero;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
Albero<String> al = new Albero ();
al.insert("lollo");
al.insert("lollo2");
al.insert("lollo3");
al.insert("lollo4");
al.insert("lollo5");
al.insert("lollo6");


for(String t: al) {
	System.out.println(t);
}
	}

}
Classe Albero e classe nodoALbero 

package ALBERO;

import java.util.Iterator;

public class Albero<T extends Comparable<T>> {


	public Albero() {
		radice=null;
	}
	
	protected nodoAlbero<T> radice;
		
		
		public void insert(String parola) {
			
			if(radice==null) {
				radice= new nodoAlbero();
				radice.sx= new Albero();
				radice.dx= new Albero();
				radice.dato = parola;
				
			}
			
			else {
				
				if(compare(parola, radice.dato) <0) radice.sx.insert(parola);
				else if(compare(parola, radice.dato) >0) radice.dx.insert(parola);
				else radice.center.insert(parola);
			}
	
		}
		
		
		public boolean trova(String parola) {
		
			if(radice==null) return false;
						
			if(parola.equals(radice.dato)) return true;
			
			else {
				if(compare(parola, radice.dato)<0) return radice.sx.trova(parola);
				else if(compare(parola, radice.dato)> 0) return radice.dx.trova(parola);
				else return radice.center.trova(parola);
			}
		}
		
		
		public Iterable<T> getInorderIterable()
		{
		return new InorderIterable<T>(radice);
		}
		


		private int compare(String o1, String o2) {
			// TODO Auto-generated method stub
			if(o1.length()== o2.length()) return 0;
			else if(o1.length()> o2.length()) return 1;
			else return -1;
		}	
	}





class nodoAlbero<T>{
	protected String dato;
	protected Albero sx,dx,center;
}

Classe in cui implemento Iterable
package ALBERO;

import java.util.Iterator;

public class InorderIterable<T extends Comparable<T>>  implements Iterable<T>

{
private nodoAlbero<T> root;
public InorderIterable(nodoAlbero<T> root)
{
this.root = root;
}

@Override
public Iterator<T> iterator()
{
return new InorderIterator<T>(root);
}

}

Classe in cui implemento Iterator 
class InorderIterator<T extends Comparable<T>>  implements Iterator<T>
{
private Stack<nodoAlbero<T>> nodesToVisit;
public InorderIterator(nodoAlbero<T> root)
{
this.nodesToVisit = new Stack<nodoAlbero<T>>();
pushLeft(root);
}



private void pushLeft(nodoAlbero<T> node)
{
while (node != null)
{
nodesToVisit.push(node);
node = node.sx.radice;
}
}




public boolean hasNext()
{
return !nodesToVisit.isEmpty();
}



@Override
public T next()
{
if (!hasNext())
throw new NoSuchElementException();
nodoAlbero<T> currentNode = nodesToVisit.pop();
pushLeft(currentNode.dx.radice);
return (T) currentNode.dx.radice.dato;
}


public void remove()
{
throw new UnsupportedOperationException();
}

}

4 Risposte

  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6270

    Re: Iterare Albero ternario di ricerca

    g.lombardo4 ha scritto:

    ma cercando di iterare con un for tutti gli elementi dell'albero si presenta un errore: Can only iterate over an array or an instance of java.lang.Iterable
    1)
    Se vuoi che il target del enhanced-for (il "for-each") sia direttamente un oggetto Albero, allora è Albero che deve implementare Iterable:

    public class Albero<T extends Comparable<? super T>> implements Iterable<T>

    E nota che ho scritto Comparable<? super T> ... perché? Perché questa è la forma più "ampia" e corretta.

    Allora sì, puoi fare for (UnTipo v : albero)

    Se invece volessi dare la possibilità di iterare in vari modi (quelli noti nella teoria degli "alberi"), cioè es. pre-order, post-order, ecc... allora basta mettere in Albero dei metodi es.

    public Iterable<T> preOrder()
    public Iterable<T> postOrder()
    ecc....

    poi es.
    for (UnTipo v : albero.postOrder())

    Naturalmente si potrebbero anche fare entrambe le cose, cioè: Albero che implementa Iterable (per l'iterazione che tu definisci come "standard"), più i metodi citati per altri modi di iterazione più particolari.


    2)
    La implementazione in Albero è comunque sbagliata riguardo il tipo di dato usato. Albero è una classe "generica", dichiara una type variable T. Questo significa che NON devi mettere

    public void insert(String parola)
    ma
    public void insert(T elemento)

    e così via.
    E ovviamente il metodo:

    private int compare(String o1, String o2)

    non ha senso. Non "sai" se sono stringhe, non puoi usare length(), ecc....

    L'unica cosa che sai è che grazie al T extends Comparable, sicuramente tutti gli oggetti trattati da Albero saranno "comparabili", quindi avranno di certo il metodo int compareTo(T altro) ed è su questo che deve basarsi tutta la logica di inserimento/ricerca.


    Non ho verificato il resto.
  • G
    g.lombardo4
    Pochi posts
    Iscritto da
    lug, 2020
    Messaggi:
    45

    Re: Iterare Albero ternario di ricerca

    Grazie della risposta Andrea,

    ho aspettato un pò prima di rispondere perchè c'erano alcune cose ancora non chiare nel mio codice ma riflettendo sulla base di ciò che hai scritto ho capito infine.
    L'unica cosa che mi resta dubbiosa è l'utilità dell'interfaccia Iterable.
    Come mai è necessaria se poi ciò che veramente importava era definire i metodi next e hasnext di Iterator ?
    Non avrei potuto far implementare ad Albero direttamente Iterator ?
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6270

    Re: Iterare Albero ternario di ricerca

    g.lombardo4 ha scritto:

    L'unica cosa che mi resta dubbiosa è l'utilità dell'interfaccia Iterable.
    Come mai è necessaria se poi ciò che veramente importava era definire i metodi next e hasnext di Iterator ?
    Iterable è concettualmente un livello sopra rispetto a Iterator. Iterable descrive solamente che un oggetto deve avere il metodo iterator() che tira fuori l'Iterator che serve materialmente per scorrere la collezione/struttura dati.
    E una collezione/struttura dati si deve poter scorrere quante volte si vuole, non solo una volta e basta. Questo è appunto il concetto: vuoi fare una iterazione? Ottieni un nuovo Iterator dal iterator(). La interfaccia Iterable è solo per fare da "astrazione" a questo concetto ("dammi l'iteratore").

    E il for-each di Java 5+ l'hanno definito per avere come target un array oppure un Iterable. In teoria il for-each potrebbe anche funzionare con solo un Iterator ma la scelta di design è stata quella.

    Non solo, Iterable essendo appunto una buona astrazione su qualunque cosa che sia "scorribile", è alla base di molte altre classi e metodi. Ad esempio da Java 8 String ha un nuovo metodo:

    public static String join(CharSequence delimiter, Iterable<? extends CharSequence> elements)

    Se tu hai un Albero<String>, allora è anche un Iterable<String>. Significa che al volo potresti ottenere una stringa che ha il "join" di tutti i valori dell'albero separati da un delimitatore, es.:
    Albero<String> alberoStr = ......

String datiAlbero = String.join(", ", alberoStr);
    Riesci a cogliere la flessibilità di questa cosa?

    g.lombardo4 ha scritto:

    Non avrei potuto far implementare ad Albero direttamente Iterator ?
    No ma principalmente per questioni concettuali (e pratiche). Implementare Iterator significa mantenere lo "stato" necessario per ricordarsi in che punto è la iterazione. Se Albero implementasse direttamente Iterator, allora dovrebbe mantenere la sua struttura dati E le informazioni sulla iterazione. Questa è una DOPPIA responsabilità che nella Object-Oriented Programming non è ben vista e non va bene.
    Oltre all'aspetto pratico che potresti farci una sola iterazione e basta.
  • G
    g.lombardo4
    Pochi posts
    Iscritto da
    lug, 2020
    Messaggi:
    45

    Re: Iterare Albero ternario di ricerca

    Adesso mi è tutto chiaro, grazie mille per il tuo tempo
Devi accedere o registrarti per scrivere nel forum
4 risposte