package buffalo.util;
import java.util.Vector;
import java.lang.Comparable;
/**
Classe générique regroupant des éléments
dans un tas selon une clé définie par l'utilisateur
de la classe. On place à la racine du tas l'élement de
plus petite clé (<CODE>a.compareTo(b)</CODE> renvoie
<CODE>1</CODE> si <CODE>a > b</CODE>)
Pour inverser le tas, il suffit de modifier
l'implémentation de la fonction de comparaison.
*/
public class Heap
{
/**
Tableau contenant tous les éléments du tas,
ce tableau est indicé à partir de
<CODE>0</CODE>.
*/
Vector elements;
/*------------------------------------------------------------*/
public Heap()
{
elements = new Vector();
}
/*------------------------------------------------------------*/
/**
Renvoie l'indice du fils droit de
l'<CODE>index</CODE>-ième
élément
du tableau, renvoie <CODE>-1</CODE> si il n'y en a pas.
*/
private int rightSon(int index)
{
if ((2*index + 1) >= getSize())
{
return -1;
}
return (2*index + 1);
}
/*------------------------------------------------------------*/
/**
Renvoie le nombre d'éléments contenus dans le tas.
*/
public int getSize()
{
return elements.size();
}
/*------------------------------------------------------------*/
/**
Renvoie l'indice du fils gauche de
l'<CODE>index</CODE>-ième
élément de tableau, renvoie
<CODE>-1</CODE> si il n'y en a pas.
*/
private int leftSon(int index)
{
if ((2*index + 2)>=getSize() )
{
return -1;
}
return (2*index + 2);
}
/*------------------------------------------------------------*/
/**
Renvoie l'indice du plus fils gauche de
l'<CODE>index</CODE>-ième
élément de tableau,
renvoie <CODE>-1</CODE> si il n'y en a pas.
*/
private int smallestSon(int index)
{
int valueOfRightSon = rightSon(index);
int valueOfLeftSon = leftSon(index);
if (valueOfRightSon == -1 )
{
return -1;
}
if (valueOfLeftSon == -1 )
{
return valueOfRightSon;
}
if (((Comparable)elements.get(valueOfLeftSon)).compareTo
(elements.get(valueOfRightSon)) == -1)
{
return valueOfLeftSon;
}
else
{
return valueOfRightSon;
}
}
/*------------------------------------------------------------*/
/**
Renvoie l'indice du père de
l'<CODE>index</CODE>-ième élément
de tableau, renvoie <CODE>-1</CODE>
si il n'y en a pas.
*/
private int father(int index)
{
if ( index <= 0 )
{
return -1;
}
return ((index-1) / 2);
}
/*------------------------------------------------------------*/
/**
Permute les deux éléments d'indices <CODE>index1</CODE>
et <CODE>index2</CODE>.
*/
private void swap(int index1, int index2)
{
Object temp;
temp = elements.get(index1);
elements.set(index1, elements.get(index2));
elements.set(index2, temp);
}
/*------------------------------------------------------------*/
/**
Place un nouvel <CODE>item</CODE> dans l'arbre sans
équilibrer ce dernier.
*/
private void addLeaf(Comparable item)
{
elements.add(item);
}
/*------------------------------------------------------------*/
/**
Remplace le premier élément par le dernier sans
équilibrer le tas.
*/
private void removeLeaf()
{
if (getSize()!=0)
{
swap(0,getSize()-1);
}
elements.remove(getSize()-1);
}
/*------------------------------------------------------------*/
/**
Retourne <CODE>0</CODE> si le tas est
équilibré
<CODE>1</CODE> si <CODE>tab[index]>tab[father]</CODE>
<CODE>2</CODE> si <CODE>tab[index]>tab[filsXxxx]</CODE>
*/
private int isBalanced(int index)
{
int valueOfRightSon = rightSon(index);
int valueOfLeftSon = leftSon(index);
int valueOfFather = father(index);
if ((valueOfFather!=-1)&&
(((Comparable)elements.get(valueOfFather)).compareTo
(elements.get(index))) == 1)
{
return 1;
}
if ((valueOfLeftSon!=-1)&&
(((Comparable)elements.get(index)).compareTo
(elements.get(valueOfLeftSon))) == 1)
{
return 2;
}
if ((valueOfRightSon!=-1)&&
(((Comparable)elements.get(index)).compareTo
(elements.get(valueOfRightSon))) == 1)
{
return 2;
}
return 0;
}
/*------------------------------------------------------------*/
/**
Equilibre le tas à partir de <CODE>index</CODE> et se
rappelle pour propager l'équilibre.
*/
private void balance(int index)
{
int valueOfFather;
int indexOfSmallestSon;
switch(isBalanced(index))
{
case 1 : valueOfFather = father(index);
swap(index, valueOfFather);
balance(valueOfFather);
break;
case 2 : indexOfSmallestSon = smallestSon(index);
swap(index, indexOfSmallestSon);
balance(indexOfSmallestSon);
break;
}
}
/*------------------------------------------------------------*/
/**
Ajoute un objet <CODE>item</CODE>
implémentant <CODE>Comparable</CODE>
dans le tas.
*/
public void add(Comparable item)
{
addLeaf(item);
balance(getSize()-1);
}
/*------------------------------------------------------------*/
/**
Fonction de suppression du premier
élément du tas.
*/
public void removeRoot()
{
Comparable formerRoot = getRoot();
removeLeaf();
balance(0);
if((getRoot()!=null)&&(getRoot().compareTo(formerRoot) == 0))
{
removeRoot();
}
}
/*------------------------------------------------------------*/
/**
Cette renvoie le premier élément du tas.
*/
public Comparable getRoot()
{
if (getSize() == 0)
{
return null;
}
return (Comparable)elements.get(0);
}
/*--------------------------------------------------------------*/
/**
Renvoie le tas au format chaîne de caractères.
*/
public String toString()
{
return elements.toString();
}
/*--------------------------------------------------------------*/
public static void main(String[] args)
{
int k = 71;
Heap tas = new Heap();
for (int i = 0; i < k; i++)
{
tas.add(new Integer((i*i*i)%k));
}
for (; tas.getRoot() != null;)
{
System.out.print(tas.getRoot() + " --> ");
tas.removeRoot();
}
}
}