package memoire;

import java.util.TreeSet;

/**
 * trunk.memoire.Tas.java
 * @author Richard Ludovic
 */
public class Tas {
	
	Bloc contenu[];// tableau de blocs.
	int nbBlocs; // nombre de blocs allou�s.
	int taille = 0;
	static final int TAILLEDEF = 10000;// nombre de blocs par d�faut.
	
	/* ************************************************************************************************* *
	 * java.util.TreeSet :                                                                               *
	 * Le java.util.TreeSet contient un ensemble d'�l�ments ordonn�s (il impl�mente �galement            *
	 * l'interface java.util.SortedSet). Les �l�ments sont ordonn�s en fonction de leur ordre naturel    *
	 * ou en fonction d'un java.util.Comparator pr�cis� � la construction du TreeSet.                    *
	 *  Complexit� : Les op�rations add, remove, contains and size sont ex�cut�es en un temps log(n).    *
	 *                                                                                                   *
	 *  @see java.util.Comparable                                                                        *
	 *  @see java.util.SortedSet                                                                         *
	 * ************************************************************************************************* */
	private TreeSet<Integer> tableAdressage; // ABR
	
	
	/*------ Constructeurs ------*/
	
	
	/**
	 * Constructeur de la classe memoire.Tas.java
	 */
	public Tas(){
		this.taille = TAILLEDEF;
		this.contenu = new Bloc[taille];
		this.nbBlocs = 0;
		tableAdressage = new TreeSet<Integer>();
		for(int i=0; i<this.taille; i++){
			tableAdressage.add(i);
		}
	}
	
	/**
	 * Constructeur de la classe memoire.Tas.java
	 * @param taille<br /> taille du tas
	 */
	public Tas(int taille){
		this.taille = taille;
		this.contenu = new Bloc[taille];
		this.nbBlocs = 0;
		tableAdressage = new TreeSet<Integer>();
		for(int i=0; i<this.taille; i++){
			tableAdressage.add(i);
		}
	}
	
	
	/*------ M�thodes --------*/
	
	/**
	 * Ajoute un tableau dans le tas
	 *
	 * @param i identifiant
	 * @param v valeur (ATTENTION : un entier)
	 * @param t type
	 * @return adresse de la premiere case du tableau dans le tas
	 */
	public int ajoutTas(String i, int v, String t){
		
		if(this.testPlace(v)){
			
			// adresse du tableau :
			int adr = getFirstFreeAdr();
			final int firstCase = adr;
			
//			// Ajout du d�placement :
//			this.ajoutValTas(adr,v); //inscrit le nombre de bloc pris par le tableau
//			tableAdressage.remove(adr); //on eleve l'adresse de la liste des libres
//			nbBlocs++; // on augmente le nombre de bloc utilises
//			
//			int aux = getFirstFreeAdr(); // prochaine adresse libre
//			this.contenu[adr].setPsuivant(aux);
//			adr = aux;
			
			// initialisation des cases avec la valeur zero des autre cases :
			
			for(int j=0;j<v-1;j++){
				this.ajoutValTas(adr,0);
				tableAdressage.remove(adr); //on eleve l'adresse de la liste des libres
				nbBlocs++; // on augmente le nombre de bloc utilises
				int aux = getFirstFreeAdr(); // prochaine adresse libre
				this.contenu[adr].setPsuivant(aux);
				adr = aux;
			}
			
			//derniere casse :
			this.ajoutValTas(adr,0);
			this.contenu[adr].setPsuivant(-1);
			tableAdressage.remove(adr); //on eleve l'adresse de la liste des libres
			nbBlocs++; 
			
			// renvoi de l'adresse pour la pile :
			return firstCase;
		}else{ // plus de place
			return -1; //ERREUR
		}
		
	}
	/**
	 * Donne l'adresse du premier bloc libre du tas
	 *
	 * @return une adresse dans le tas
	 */
	private int getFirstFreeAdr(){
		return tableAdressage.first();
	}
	/**
	 * Verifie que la taille du tableau est inferieur a la taille libre totale du tas
	 *
	 * @param tailleTab taille du tableau
	 * @return vrai si il y a la place, faux sinon
	 */
	private boolean testPlace(int tailleTab){
		return (tailleTab+1 <= (this.taille - this.nbBlocs));
	}
	/**
	 * Ajoute ou modifie la valeur contenu dans un bloc du tas 
	 *
	 * @param adr adresse du bloc dans le tas
	 * @param val valeur a affecter
	 */
	private void ajoutValTas(int adr,int val){
		try{
			if(this.contenu[adr] == null){// le bloc n'est pas encore affect�
				this.contenu[adr] = new Bloc(val);
				this.contenu[adr].setMarkflag(true);
			}else{ // bloc deja affecte => modification de la valeur
				this.contenu[adr].setValeur(val);
				this.contenu[adr].setMarkflag(true);
			}
			tableAdressage.remove(adr); //on eleve l'adresse de la liste des libres
			nbBlocs++; // on augmente le nombre de bloc utilises
		}catch(Exception e){
			e.printStackTrace();
		}
		
	}
	/**
	 * Desaloue un bloc
	 *
	 * @param adr adresse du bloc dans le tas
	 */
	public void libererBloc(int adr){
		this.contenu[adr] = null;
		tableAdressage.add(adr); //ajoute l'adresse de la liste des libres
		nbBlocs--; // diminue le nombre de bloc utilises
	}
	
	/**
	 * Enleve un tableau du tas
	 *
	 * @param adr
	 */
	public void retirerTas(int adr){	
		if(this.contenu[adr] != null){		
			do{ 
				libererBloc(adr);
				adr = this.contenu[adr].getPsuivant();
			}while(this.contenu[adr].getPsuivant() != -1);
		} 			
	}
	
	/**
	 * Deplace un objet du Tas.
	 *
	 * @param adr1 adresse source
	 * @param adr2 adresse destination
	 * @return vrai si l'opperation reussie
	 */
	public boolean deplacerObjet(int adr1, int adr2){
		
		// verification que l'adresse destination est libre :
		if(!this.tableAdressage.contains(adr2)) return false;
		// verification que l'adresse source contient un objet :
		if(this.tableAdressage.contains(adr1)) return false;
		
		this.contenu[adr2] = new Bloc(this.contenu[adr1]);
		this.retirerTas(adr1);

		return true;
	}
	
	/**
	   * Affiche le Tas dans une chaine de caracteres
	   * @return une chaine de caracteres
	   */
	public String toString(){
		String buf ="";
		
		for(int i=0; i<this.taille; i++){
			if(i%10 == 1 && i !=1) buf +="\n";
			if(this.contenu[i] == null){
				buf +="[NULL|NULL]";
			}else{
				buf += this.contenu[i].toString();
			}
			
		}
		return buf;	
	}
	
	/* test*/
	public static void main(String[] args) {
		
		Tas tas = new Tas(1000);
		

		 System.out.println("D�but du test du tas");
		 
		 int adr = tas.ajoutTas("tab1", 10, "tab");
		 System.out.println("adresse de tab1 = "+adr);
		 System.out.println(tas.toString());
		 
		 int adr2 = tas.ajoutTas("tab2", 50, "tab");
		 System.out.println("adresse de tab2 = "+adr2);
		 System.out.println(tas.toString());
		 
		 System.out.println("fin du test du tas !");
	}
}
