Manipulation 4

Dans cette séance nous allons reprendre le programme que nous avons écris lors de la précédente manipulation. Nous utilisions une structure de type Ensemble (de taille dynamique) afin de stocker les différents éléments de notre repère. Pour l’implémenter nous avions décidé d’utiliser en interne des tableaux de tailles fixes. Il fallait donc gérer l'agrandissement de ces tableaux et la position des éléments. L'objectif de cette manipulation est de comprendre l'intérêt des interfaces génériques pour séparer les fonctionnalités de l'implémentation. Nous allons donc définir notre propre interface avec deux types d'implémentations. Pour rappel, voici le code de la classe qui permet de tester les ensembles :

public class TestEnsembleElementRepere {
	public static void main(String[] args) {
		EnsembleElementRepere ens = new EnsembleElementRepere();
		long t0 = System.currentTimeMillis();
		for(int i = 0; i < 10000; i++) {
			ens.ajouter(new Point("Point", Couleur.auHasard(), (int) (Math.random() * 20), (int) (Math.random() * 20)));
		}
		long t1 = System.currentTimeMillis();
		long time = t1 - t0;
		System.out.println(ens.nombreElements() + " éléments ajoutés en: " + time + " ms.");
	}
}

Définition de l'interface

Tout d'abord il faut créer une interface EnsembleElementRepere qui propose les définitions de méthodes suivantes :

public interface EnsembleElementRepere {
	ElementRepere recuperer(int index);

	void ajouter(ElementRepere element);

	int nombreElements();
}

Implémentation par tableaux de tailles fixes

La première implémentation de cette interface doit utiliser des tableaux de tailles fixes. Il faut donc définir une classe EnsembleElementRepereTableau qui implémente cette nouvelle interface. Il s'agit donc d'une implémentation à l'aide de tableaux de tailles fixes. Commencez par implémenter cette classe en réutilisant le code de la manipulation précédente.

Implémentation par liste chainée

Voici une implémentation d'ensemble à l'aide d'une liste chainée :

public class EnsembleElementRepereChaine {
	ElementRepereCell tete;

	@Override
	public ElementRepere recuperer(int index) {
		ElementRepereCell c = tete;
		int cpt = 0;
		while (c != null) {
			if ( cpt == index)
				return c.valeur;
			++cpt;
			c = c.suivante;
		}
		return null;
	}

	@Override
	public void ajouter(ElementRepere element) {
		tete = new ElementRepereCell(element, tete);
	}

	@Override
	public int nombreElements(){
		ElementRepereCell c = tete;
		int cpt = 0;
		while (c != null) {
			++cpt;
			c = c.suivante;

		}
		return cpt;
	}
}

class ElementRepereCell  {
	ElementRepere valeur;

	ElementRepereCell suivante;

	ElementRepereCell(ElementRepere valeur, ElementRepereCell suivante) {
		this.valeur = valeur;
		this.suivante = suivante;
	}
}

Vous devez modifier cette classe pour qu'elle implémente l'interface définie auparavant.

Utilisation de l'interface et des implémentations

Modifiez maintenant le code de la classe de test pour qu'elle utilise l'implémentation basée sur les tableaux. Testez les performances. Modifiez le code pour utiliser l'implémentation basée sur la liste chaînée. Testez les performances. Que remarquez vous pour les performances? Avez vous trouvé difficile de changer une implémentation par une autre?

public class TestEnsembleElementRepere {

	public static void main(String[] args) {
		EnsembleElementRepere ens;
		// Tableaux de tailles fixes
		// ens = new EnsembleElementRepereTableau();

		// Liste chaînée
		// ens = new EnsembleElementRepereChaine();

		long t0 = System.currentTimeMillis();
		for(int i = 0 ; i < 10000 ; i++) {
			ens.ajouter(new Point("Point", Couleur.auHasard(), (int) (Math.random()*20), (int) (Math.random()*20)));
		}
		long t1 = System.currentTimeMillis();
		long time = t1 - t0;
		System.out.println(ens.nombreElements() + " point ajoutés en: " + time + " ms.");
	}

}

Généricité de l'interface

Modifiez l'interface précédemment définie à l'aide de type générique afin qu'elle accepte le stockage de n'importe quel type d'objets. Renommez cette interface EnsembleElement. Une fois l'interface modifiée, veuillez adaptez les deux classes qui l'implémentent. Renommez les EnsembleElementTableau et EnsembleElementChaine. Finalement, adaptez le code de la classe de test pour utiliser ces nouvelles classes et interfaces. Attention, pour l'implementation à l'aide de tableaux, il faut que le tableau interne soit un tableau d'objets, et il faut utiliser des casts.

public interface EnsembleElement<E> {
	E recuperer(int index);

	void ajouter(E element);

	int nombreElements();
}

public class TestEnsembleElement {
	public static void main(String[] args) {
		EnsembleElement<ElementRepere> ens;
		// Tableaux de tailles fixes
		// ens = new EnsembleElementTableau<>();

		// Liste chaînée
		// ens = new EnsembleElementChaine<>();

		long t0 = System.currentTimeMillis();
		for(int i = 0; i < 10000; i++) {
			ens.ajouter(new Point("Point", Couleur.auHasard(), (int) (Math.random() * 20), (int) (Math.random() * 20)));
		}
		long t1 = System.currentTimeMillis();
		long time = t1 - t0;
		System.out.println(ens.nombreElements() + " point ajoutés en: " + time + " ms.");
	}

}