package inf2120ete2016;

import java.util.List;

/**
 * Chaque ABRNoeud est a la fois un noeud et un arbre.
 * Ils contiennent un pointeur vers le sous arbre de gauche et un autre
 * vers le sous arbre de droite.
 * 
 * @author
 *	//version de Guy Lapalme (GL) de la classe BSTNode de Watt&Browm (Nov 2001)
 *	//version générique en juin 2010 et Novembre 2011
 *	//traduction francais : Bruno Malenfant, Juillet 2016
 *
 * @param < E >
 *   type generique des elements contenus dans l'arbre binaire de recherche.
 *   Ils doivent etre comparable.
 */
public class ABRNoeud< E extends Comparable< E > > {
	
		// CHAMPS
	
		/**
		 * L'élément contenu dans ce noeud.
		 * @invariant
		 * element != null
		 */
		protected E _element;
		
		
		/**
		 * Le pointeur vers l'arbre de gauche.
		 * @invariant
		 * $\forall x \in gauche | x < element$
		 */
		protected ABRNoeud< E > _gauche;
		
		
		/**
		 * Le pointeur vers l'arbre de droite.
		 * @invariant
		 * $\forall x \in droite | x > element$
		 */
		protected ABRNoeud< E > _droite;

		
		// CONSTRUCTEURS
		
		/**
		 * Constructeur vide
		 * Aucun arbre vide ne devrait etre constuit, ce constructeur 
		 * est utilisé pour JUnit.
		 */
		public ABRNoeud() {}

		/**
		 * Construit un arbre contenant un seul élément à la racine.
		 * @param element
		 *   L'élément qui sera placé à la racine.
		 */
		public ABRNoeud( E element ) {
			assert element != null;
			
			this._element = element;
			this._gauche = null;
			this._droite = null;
		}

		
		// METHODE
		
		/**
		 * Construit une version String de l'arbre pour l'affichage.
		 */
		public String toString() {
			StringBuffer sb = new StringBuffer();
			sb.append( _element );
			
			if( _gauche != null || _droite != null ) {
				sb.append( "(" ).append( _gauche == null ? "/" : "" + _gauche ).append( "," ).
				                 append( _droite == null ? "/" : "" + _droite ).append( ")" );
			}
			return "" + sb;
		}

		
		/**
		 * Permet d'extraire l'élément noeud courrant.
		 * @return
		 *   L'élément du noeud.
		 */
		public E getElement() {
			return _element;
		}

		
		/**
		 * Calcule le nombre de noeud que contient cet arbre.
		 * @return
		 *   Le nombre de noeud de l'arbre.
		 */
		public int taille() {
			return 1 + ( _gauche == null ? 0 : _gauche.taille() )
			         + ( _droite == null ? 0 : _droite.taille() );
		}

		
		/**
		 * Retourne les éléments de l'arbre binaire.
		 * @param list
		 *   Doit être appelé avec une liste vide.
		 *   list != null
		 * @return
		 *   Une liste contenant les éléments de l'arbre en ordre.
		 */
		public List< E > elements( List< E > list ) {
			assert list != null;
			
			if( _gauche != null ) {
				_gauche.elements( list );
			}
			
			list.add( _element );
			
			if( _droite != null ) {
				_droite.elements( list );
			}
			
			return list;
		}

		
		/**
		 * Trouve le noeud contenant un élément cible.
		 * @param cible
		 *   L'élément cible à trouver
		 *   cible != null
		 * @return
		 *   Un pointeur sur l'élément recherché ou un pointeur null
		 *   si l'élément n'est pas présent dans l'arbre.
		 */
		public ABRNoeud<E> chercher( E cible ) {
			assert cible != null;
			
			ABRNoeud< E > resultat = null;
			int direction = cible.compareTo( _element );
			
			if ( direction == 0 ) {
				resultat = this;
			} else if ( direction < 0 ) {
				resultat = ( _gauche == null ) ? null : _gauche.chercher( cible );				
			} else {
				assert direction > 0;
				
				resultat = ( _droite == null ) ? null : _droite.chercher( cible );
			}
			
			return resultat;
		}

		
		/**
		 * Ajouter un element dans l'arbre.
		 * Aucun noeud n'est ajouté si l'élément était déjà présent.
		 * @param element
		 *   l'élément à ajouter
		 *   element != null
		 * @return
		 *   Cette méthode retourne un pointeur sur l'arbre résultant.
		 */
		public ABRNoeud< E > inserer( E element ) {
			assert element != null;
			
			int direction = element.compareTo( _element );
			
			if ( direction < 0 ) {
				_gauche = ( _gauche == null ) ? new ABRNoeud< E >( element ) : _gauche.inserer( element );
			} else if ( direction > 0 ) {
				_droite = ( _droite == null ) ? new ABRNoeud< E >( element ) : _droite.inserer( element );
			}
			
			return this;
		}

		
		/**
		 * Supprimer un element de l'arbre
		 * @param element
		 *   L'élément à supprimer
		 *   element != null
		 * @return
		 *   La racine de l'arbre duquel l'élément à été supprimé.
		 */
		public ABRNoeud<E> supprimer( E element ) {
			assert element != null;

			ABRNoeud<E> resultat = this;
			
			int direction = element.compareTo( _element );
			
			if( direction < 0 ) {
				if( _gauche != null ) {
					_gauche = _gauche.supprimer( element );
				}
			} else if( direction > 0 ) {
				if( _droite != null ) {
					_droite = _droite.supprimer( element );
				}
			} else {
				assert direction == 0;
				
				if( _gauche == null ) {
					resultat = _droite;
				} else if( _droite == null ) {
					resultat = _gauche;
				} else {
					assert _gauche != null && _droite != null;
					
					// Aller chercher l'element suivant et le supprimer.
					_element = _droite.elementPlusAGauche();
					_droite = _droite.supprimer( _element );
				}
			}
			
			return resultat;
		}


		// METHODES AUXILIAIRES

		
		/**
		 * Ajoute n espace dans un StringBuilder.
		 * Utilisé par le PrettyPrinter "pprint".
		 * @param sb
		 *   Le StringBuilder.
		 *   sb != null
		 * @param n
		 *   Le nombre d'espace a ajouter.
		 *   n >= 0
		 */
		private void blanc( StringBuilder sb, int n ) {
			assert sb != null;
			assert n >= 0;
			
			int i;
			
			for( i = 0; i < n; ++ i ) {
				sb.append( ' ' );
			}
		}

		
		/**
		 * Construit une version affichable de l'arbre, plus jolie que le toString.
		 * @param sb
		 *   Le StringBuilder ou la version affichable sera construite.
		 *   sb != null 
		 * @param indent
		 *   L'indentation de l'arbre.
		 *   indent >= 0
		 * @return
		 *   Le StringBuilder contenant la version affichable de l'arbre.
		 */
		public StringBuilder pprint( StringBuilder sb, int indent ) {
			assert sb != null;
			assert indent >= 0;
					
			int newIndent = indent + 2;

			if( _droite != null ) {
				_droite.pprint( sb, newIndent );
			}
			
			blanc( sb, indent );
			sb.append( _element + " " ).append( '\n' );
			
			if( _gauche != null ) {
				_gauche.pprint( sb, newIndent );
			}
			
			return sb;
		}

		
		/**
		 * Retrouve l'element le plus a gauche de ce noeud
		 * @return
		 *   L'element le plus a gauche, ou l'element lui meme s'il n'y a rien a gauche.
		 */
		protected E elementPlusAGauche() {
			return ( _gauche == null ) ? _element : _gauche.elementPlusAGauche();
		}
}