TRI PAR TAS GÉNÉRIQUE. RAPIDE ET EFFICACE.

/*
 * Implémentation du tris par tas générique. Bloomwhite 2002-2004
 *
 *	Simple fonction (en fait c'est un objet utilisé en fonction).
 *	exemple: TriTas<int>(tab, taille(tab));	// ici, tab est un tableau d'entiers (int).
 *
 *	Entrées:
 *	Le premier argument est un tableau de type C (vecteur). Il peut être de type quelconque.
 *	Le second argument est la taille du tableau en nombre d'éléments.
 *		(ou du dernier élément +1 à trier)
 *	Le troisième argument est optionnel:
 *		c'est une fonction de comparaison selon laquelle va être trié le tableau,
 *		si cette fonction est de type >, le tableau sera trié dans l'ordre croissant.
 *		Si elle n'est pas précisée, l'opérateur > sera utilisé par défaut;
 *		il faudra alors que cet opérateur soit définit pour le type contenu dans le tableau.
 *
 *	Sorties:
 *	Aucune sortie. Le tableau sera trié.
 *
 *		A Public OpenSource Project.
 */

#ifndef _TriTas_H_
#define _TriTas_H_


// Je fourni la fonction utilisée par défaut pour le tri.
// Pour des raisons aussi bien obscures que mystérieuses, j'ai pas pu la mettre dans la classe.
template<class Type>
inline bool _compare_defaut_tritas	(Type a, Type b) { return (a>b); }
// En fait, je pense que c'est parce qu'elle est utilisée en argument par défaut dans la classe.


template<class Type>
class TriTas
{
public:
	TriTas(Type*, int, bool (__cdecl*)(Type, Type)=_compare_defaut_tritas);	// Tableau,taille,fct
	~TriTas() {};
private:
	inline void echange(Type& a, Type& b)	{	Type temp= a; a= b; b= temp;	}
	bool (*compare)	(Type, Type);	// Donnée membre et non fonction (pointeur sur fonction).

	void entasser	(int =0);	// Par défaut entasser la racine.
	void construit	();			// Tri.

	int _taille;				// Taille du tableau.
	Type* _a;					// Tableau à trier.
};


template<class Type>
TriTas<Type>::TriTas(Type* a, int taille, bool (*comp)(Type, Type)) : _taille(taille), _a(a)
{
	compare = comp;
	construit();							// D'abord préparation
	for (--_taille; _taille > 0; --_taille)
	{
		echange(_a[_taille],_a[0]);			// Puis tri.
		entasser();
	}
}

template<class Type>
void TriTas<Type>::entasser(int noeud)
{
	int	max,
		gauche= 2*noeud+1,
		droite= gauche+1;
	max = noeud;
	if (gauche<_taille && compare(_a[gauche],_a[noeud]))	max = gauche;
	if (droite<_taille && compare(_a[droite],_a[max])  )	max = droite;

	if (max != noeud)
	{
		echange(_a[max],_a[noeud]);
		entasser(max);
	}
}

template<class Type>
void TriTas<Type>::construit()
{
	int last;
	for(last= _taille/2 - 1; last>=0; --last)	// on commence au dernier ayant
		entasser(last);							// un fils jusqu'au premier (la racine)
}

#endif //_TriTas_H_