package fr.eisti.arbre;

import java.util.*;
import java.io.Serializable;

// classe masquée à l'exterieur du package
// il faut passer obligatoirement par la méthode iterator de la classe arbre
// pour en obtenir une instance
class IterateurOrdonneArbre<V extends Comparable<V>&Serializable> implements Iterator<V> {

	// la file des éléments à parcourir
	// on peut également faire une file de noeud, si on préfère
	// parcourir les noeuds plutôt que les valeurs
	private Deque<V> file;
	
	IterateurOrdonneArbre(Arbre<V> arbre) {
		// création de la file
		file = new LinkedList<V>(); // ou ArrayDeque
		// remplissage de la file
		initParcours(arbre);
	}
	
	private void initParcours(Arbre<V> arbre) {
		// ajout des éléments plus petits en tête
		if (arbre.aFilsGauche()) {
			initParcours(arbre.getFilsGauche());
		}
		// ajout de la valeur du noeud courant
		file.offerFirst(arbre.getValeur());
		// ajout des éléments plus grands
		if (arbre.aFilsDroit()) {
			initParcours(arbre.getFilsDroit());
		}
	}
	
	@Override
	public boolean hasNext() {
		return (!file.isEmpty());
	}
	
	@Override
	public V next() {
		if (file.isEmpty()) {
			throw new NoSuchElementException();
		}
		// on renvoie le plus petit élement en queue de file
		return 	file.pollLast();
	}
	
	@Override
	public void remove() {
		throw new UnsupportedOperationException();
	}
}