Première partie

Objectifs d'apprentissage

  • Concevoir une liste doublement chaînée possédant aussi un noeud factice.
  • Modifier l'implémentation d'une liste chaînée afin d'y ajouter des méthodes.
  • Résoudre des problèmes exigeant une bonne compréhension des interfaces.
  • Comprendre le principe d'itérateur.

Itérateurs

Un itérateur est un patron de conceptualisation qui nous permet de parcourir une collection d’éléments afin de pouvoir interagir avec ces éléments. Un itérateur nous permet d’accéder à un élément, puis à partir de cet élément, on peut accéder au prochain et ainsi de suite jusqu’à ce que la collection ait été épuisée.

En java, l’interface Iterator qui possède les méthodes hasNext(), next() et remove().

    hasNext() : retourne vrai si l’itérateur a un procain element next() : retourne le prochain élément ou lance NoSuchElementException s’il n’y a pas de prochain élément. remove() : enlève l’élément de la collection. Doit être appelé après l’appel à la méthode next().

Afin de démontrer l’utilisation d’un itérateur, nous allons utiliser la classe java.util.LinkedList. LinkedList est une liste simplement chainée qui implémente l'interface iterable qui possède la méthode iterator(). La méthode iterator() retourne un objet implémentant l'interface Iterator.

Une fois que nous avons cet itérateur, nous pouvons parcourir tous les éléments de la liste al. Pour ce faire, nous utilisons une boucle while avec la condition que hasNext() retourne vrai. Nous pouvons ensuite imprimer tous les éléments de la liste.

import java.util.*;

public class IteratorDemo{
	public static void main(String args[]) {
		// Create an array list
		LinkedList<String> al = new LinkedList<String>();
		  
		// add elements to the array list
		al.add("dog");
		al.add("bird");
		al.add("fish");
		al.add("cat");
		al.add("monkey");
		al.add("lizard");

		// Use iterator to display contents of al
		System.out.print("Contents of al: ");
		Iterator<String> itr = al.iterator();
		
		while(itr.hasNext()) {
		   String element = itr.next();
		   System.out.print(element + " ");
		}
	}
}
  

Notez qu’avec un itérateur de base nous ne pouvons pas modifier les éléments de la liste. Par contre, plusieurs implémentations de l’interface Iterator ont des méthodes afin de pouvoir modifier les éléments et d'autres opérations. Par exemple, une implémentation de Iterator, ListIterator, possède des méthodes additionnelles telles que add, hasPrevious, previous, set et bien d’autres.

Exercice 1

Modifiez le code précédent afin d’imprimer seulement les éléments de la liste al qui se retrouvent avant la chaîne de caractère « cat » dans la liste (imprimer tous les éléments avant que « cat » soit rencontré).

Indice : modifiez la condition while

La boucle for each

La boucle for each agit comme un itérateur. Il nous permet d’agir directement sur les éléments (nous n’avons pas besoin d’utiliser de méthode comme set()).

La syntaxe de la boucle for each est la suivante :


for(type elem:collection){
	//more code
}
  

Où :

  • type : le type des éléments du contenant
  • elem : est le nom de la variable qui représente chaque élément dans la boucle
  • collection : est le nom de variable de la collection que nous voulons itérer.

Par défault, cette boucle parcourra tous les éléments, par contre, si nous ne voulons pas tous les parcourir, nous pouvons utiliser la commande break entourée d’une condition pertinente pour sortir de la boucle.

Voici une solution de l’exercice 1 précédent, mais résolu avec la boucle for each.

import java.util.*;

public class IteratorDemo{
	public static void main(String args[]) {
		// Create an array list
		LinkedIn<String> al = new LinkedIn<String>();
		  
		// add elements to the array list
		al.add("dog");
		al.add("bird");
		al.add("fish");
		al.add("cat");
		al.add("monkey");
		al.add("lizard");
        
		System.out.println("\nSolving using augmented for loop: ");
		
		for(String element:al){
			if(element.equals("cat")){
				break;
			}
			System.out.print(element + " ");
		}
	}
}
  

File circulaire

Les files circulaires sont un type de files qui implémente le principe de premier arrivé premié servi (Fisrt In First Out - FIFO). Dans ces files, le dernier élément est relié au premier afin de faire un cercle. Cette file a une variables d'instance pour la tête de la file (head) et une pour la queue de la file (tail).

Lorsque l’on ajoute un élément en utilisant enqueue(), on ajoute un élément à la position de la queue (tail) et on incrémente le pointeur tail. Lorsque l’on enlève un élément en utilisant dequeue(), on enlève et retourne l’élément a la position de la tête (head) et incrémente le pointeur de la tête.

Voici une représentation graphique d’une file circulaire. Nous pouvons soit la représenter comme un tableau ou le dernier élément est lié au premier, ou encore comme un tableau circulaire.

une representation visuel des files circulaire.

Figure 1 : Représentation visuelle des files circulaires.

Les listes simplement et doublement chaînées

Rappel: Tel que vu en classe, il existe plusieurs implémentations d'une liste avec des éléments chaînés. Nous vous avons notamment présenté les listes simplement et doublement chaînées en classe. Ces implémentations, bien que semblables dans les deux cas, possèdent des différences notables.

D'un coté, les listes simplement chaînées relient chaque élément à leur prochain, et ce, jusqu'au dernier élément qui aura pour suivant (next) null.

D'un autre côté, les listes doublement chaînées permettent l'implémentation plus rapide de certaines méthodes grâce au lien qui relie chaque élément à son précédent. Le dernier élément aura, telle la liste simplement chaînée, un prochain (next) null, tout le comme le premier élément qui a un précédent (prev) null.

Il y a aussi possibilité d'implémenter une liste simplement ou doublement chaînée avec un noeud factice, c'est-à-dire un noeud qui n'aura aucune valeur (null) et qui sera placé au début de la liste. Ce dernier permet de simplifier l'implémentation de méthodes en réduisant le nombre de cas spéciaux et rend aussi la liste circulaire puisque le premier élément de la liste aura ce noeud en élément précédent et le dernier élément l'aura en élément suivant.

Testez votre compréhension des différentes implémentations

Question 1.0 :

Décrivez la figure suivante. Notamment, s'agit-il d'une liste simplement ou doublement chaînée? Comment s'appelle la technique utilisée (un noeud ..)?

Voir l'image

Question 1.1 :

Vrai ou faux? Il est possible de parcourir une liste simplement chaînée dans les deux directions efficacement.

Réponse
Question 1.2 :

Que devons-nous utiliser pour faciliter l'ajout d'un élément à la fin d'une liste?

Réponse
Question 1.3 :

Vrai ou faux? Une liste circulaire possédant un noeud factice a plusieurs cas particuliers.

Réponse
Question 1.4 :

Dans quel contexte l'utilisation de l'implémentation d'une liste à base de tableaux est-elle avantageuse à celle d'une liste à base d'éléments simplement chaînés? Nommez 2 méthodes.

Réponse
Question 1.5 :

Avons-nous besoin d'une variable de référence tail dans le cas d'une liste circulaire doublement chaînée?

Réponse
Question 1.6 :

Vrai ou faux? Pour implémenter une liste chaînée, nous pouvons tout simplement utiliser un tableau dynamique.

Réponse
Question 1.7 :

Voici le constructeur de la classe imbriquée Node d'une List. Identifiez si la liste est simplement ou doublement chaînée.

//constructor
	private Node(T value, Node next) {
		this.value = value;
		this.next = next;
	}
Réponse
Question 1.8 :

Vrai ou Faux? L'utilisation d'une file à base d'éléments chaînés est avantageuse à celle à base d'un tableau, car il n'y a pas de nombre maximal d'éléments dans la liste.

Réponse
Question 1.9 :

Qu'est-ce que le bout de code suivant effectue dans une liste circulaire doublement chaînée? Considérez que la variable current a été préalablement déclarée.

current = head.prev; 
while (current != head) { 
current = current.prev; }
Réponse

Deuxième partie

OrderedStructure

Vous êtes maintenant prêt à appliquer vos connaissances. Consultez les notes du cours concernant l'implémentation d'une liste doublement chaîné au besoin. Référez-vous au image en appendice afin de mieux visualiser votre liste. N'hésitez pas à faire vos propre dessins lorsque vous écrivez votre implémentation!

Pour ce laboratoire, vous devez créer une implémentation de l'interface OrderedStructure à l'aide de noeuds doublement chaînés et d'un noeud factice. L'interface OrderedStructure déclare les méthodes suivantes:

public interface OrderedStructure {
	int size() ;
	boolean add(Comparable element) throws IllegalArgumentException;
	Object get(int pos) throws IndexOutOfBoundsException;
	void remove(int pos) throws IndexOutOfBoundsException;
}

Les classes implémentant cette interface doivent sauvegarder les éléments en ordre croissant les éléments. L'ordre de ces derniers est défini par l'implémentation de la méthode compareTo(Object other) que déclare l'interface Comparable. Les classes Integer et String implémentent toutes les deux cette interface et peuvent donc servir pour vos tests.

IMPORTANT : puisque l'objectif principal du laboratoire est de bien maîtriser les concepts liés à l'implémentation des listes chaînées, par souci de simplicité, nous n'utiliserons pas le concept de type générique («generics»). Ainsi,

  1. Le compilateur produira quelques avertissements
  2. Mais surtout, les utilisateurs de la méthode get devront forcer une conversion de type puisque la valeur de retour est de type Object.

Il y a à la fin du laboratoire un exercice (optionnel) où l'on vous demande de produire un type générique. La solution sera publiée la semaine prochaine.

OrderedList

  1. Créez une classe OrderedList qui réalisera l'interface OrderedStructure. L'implémentation de OrderedList doit utiliser des noeuds doublement chaînés, ainsi qu'un noeud factice. La classe doit posséder une référence head vers le noeud factice. De plus, votre implémentation doit lancer toutes les exceptions nécessaires. Voici les fichiers à partir desquels vous pouvez commencer votre travail :

    Nous allons développer cette implémentation étape par étape, de haut en bas. C'est-à-dire que nous allons d'abord implémenter les éléments de haut niveau (variables d'instance, classe imbriquée statique, et des coquilles pour chacune des méthodes). Une fois tout ça en place, nous implémenterons le corps des méthodes, une à une.

    1. Premièrement, vous devez créer une définition initiale de OrderedList. Pour l'instant, nous ignorons l'implémentation des méthodes afin de nous concentrer sur les variables et la nécessité d'une classe « static » imbriquée afin de représenter les noeuds de la liste. Pour satisfaire les exigences du compilateur, toutes les méthodes de l'interface OrderedStructure doivent être déclarées. La classe doit donc contenir une classe Node, les variables d'instance et des déclarations vides pour chacune des méthodes de l'interface. Vous ne devez pas utiliser de variables int size. D'autant plus, sachez que notre classe Node doit sauvegarder des valeurs de type Comparable

      Attention, le compilateur n'acceptera pas des déclarations vides pour les méthodes retournant une valeur. Vous pourriez inclure un énoncé de retour bidon, par exemple retourner la valeur -99 pour la méthode size, sachant que cet énoncé sera remplacé par une implémentation complète éventuellement.

      Cependant, il se peut que vous oubliiez de faire ces changements et l'ensemble de la classe deviendrait difficile à déboguer. Pour cette raison, je préfère créer une définition initiale ne contenant que l'énoncé suivant.

      int size(){
      	throw new UnsupportedOperationException("not implemented yet!");
      }

      Faites de même pour chacune des méthodes de votre classe.

      Ça nous permet de compiler la classe et de travailler sur l'implémentation des méthodes une à une. Toute tentative d'utiliser une méthode qui n'a pas encore d'implémentation sera signalée par une exception ! Vous pouvez demander des explications supplémentaires à votre aide à l'enseignement si nécessaire.

      Créez une classe test, OrderedListTest. Pour l'instant, elle ne contient qu'une méthode principale déclarant une variable de type OrderedList, désignant un objet OrderedList.

      Assurez vous que l'implémentation partielle de OrderedList comprenne tous les éléments ci-haut et qu'elle compile parfaitement. Lorsque ce sera fait, vous pouvez procéder à la prochaine étape, soit l'implémentation de la méthode size.

    2. Implémentez la méthode size(). Pour ce faire, remplacez l'énoncé throw par une implémentation itérative traversant la liste et comptant ses éléments.Ajoutez un test à la classe OrderedListTest afin de vous assurer que la méthode fonctionne pour la liste vide. Nous ajouterons d'autres tests lorsque nous aurons une méthode add.
    3. Implémentez la méthode boolean add(Comparable obj) . La méthode ajoute un élément à la liste en ordre croissant selon l'ordre naturel imposé par la classe de l'objet (i.e. vous devez utiliser sa méthode compareTo). Elle retourne true si l'élément a été ajouté à cette liste ordonnée, false sinon.
    4. Ajoutez quelques tests afin de valider la méthode add. Il sera difficile d'évaluer la méthode proprement, mais au moins la taille de la liste devrait s'accroître à mesure que des éléments y sont ajoutés à la liste.
    5. Implémentez Object get(int pos). Cette dernière retourne l'élément se trouvant à la position spécifiée de cette liste ordonnée ; le premier élément se trouve à la position 0. Cette opération ne doit pas transformer la liste.
    6. Ajoutez des tests afin de valider les méthodes get et add. Nous sommes maintenant en bien meilleure position pour évaluer les méthodes add, get et size. En particulier, nous pouvons ajouter des éléments, utiliser une boucle afin d'accéder aux éléments un à un à l'aide de la méthode get. Assurez-vous que toutes les méthodes fonctionnent bien avant de poursuivre. N'oubliez pas que votre méthode get retourne un élément de type Object, vous devrez donc forcer sa conversion dans le type choisi lors de vos tests (cast).
    7. Implémentez void remove(int pos). La méthode retire l'élément à la position spécifiée de cette liste ordonnée ; le premier élément se trouve à l'index 0.
    8. Ajoutez des tests afin de valider la méthode remove. Assurez-vous que cette méthode fonctionne (ainsi que les autres) avant de poursuivre.

    Nous avons maintenant une implémentation complète de l'interface OrderedStructure.

  2. Ajoutez la méthode d'instance void merge(OrderedList other) qui ajoute tous les éléments de la liste other à cette liste tout en préservant l'ordre des éléments. Par exemple, si a et b sont deux listes ordonnées telles que a contient “D”, “E” et “G”, et b contient “A”, “C”, “D” et “F”, alors l'appel a.merge(b) transforme a de sorte qu'elle contient maintenant les éléments suivants “A”, “C”, “D”, “D”, “E”, “F” et “G” , tandis que b demeure inchangée par cet appel. La classe String implémente l'interface Comparable et peut être utilisée pour tester votre méthode.

    Cet exercice a pour but d'apprendre à traverser et transformer des listes doublement chaînées. Ainsi, vous ne devez pas utiliser des méthodes auxiliaires, en particulier, n'utilisez pas la méthode add !

    Votre implémentation doit traverser les deux listes et insérer les éléments (valeurs) de l'autre liste dans celle-ci ; en ordre croissant. Rappelez-vous qu'il est préférable de développer ces habiletés maintenant, plutôt qu'à l'examen final !

  3. Sujet avancé et optionnel :
    1. Utilisez votre implémentation de la classe OrderedList comme point de départ afin de créer un type générique («generics») qui réalise l'interface OrderedStructure suivante :
      public interface OrderedStructure <T extends Comparable<T>> { 
          int size(); 
          boolean add(T elem) throws IllegalArgumentException; 
          T get(int pos) throws IndexOutOfBoundsException; 
          void remove(int pos) throws IndexOutOfBoundsException; 
      }

      L'un des avantages marqués de cette implémentation sera que tous les éléments de la liste auront le même type. Ce qui est très important pour la méthode compareTo.

    2. Implémentez maintenant votre classe OrderedList sans utiliser de noeud factice. Que constatez-vous? Bien que plus longue, cette implémentation vous apprendra l'importance de bien traiter chaque cas particulier un à un, et ce, dans chaque méthode.

Appendice

Une liste vide.

Figure 1 : Une liste vide.
Une liste contenant un seul élément.

Figure 2 : Une liste contenant un seul élément.
Une liste contenant deux éléments.

Figure 3 : Une liste contenant deux éléments.
Une liste contenant trois éléments.

Figure 4 : Une liste contenant trois éléments.

 

Troisième partie

Section plus avancée : ce concept vous sera utile pour le reste de vos études et possiblement au travail.

Objectifs d'apprentissage

  • Comprendre le concept de version de contrôle et son importance.
  • Apprendre les bases du système de contrôle de versions Git ainsi que son service d'hébergement GitHub.
  • Apprendre les commandes de base de Git, telles que git init, git add, git commit, git push, git pull.
  • Présenté à fin d'introduction pour les étudiants n'ayant jamais appris à utiliser Git auparavant.

Pourquoi apprendre Git?

Un problème commun lors que l'on manipule de l'information stockée sur un ordinateur est la gestion des changements. Par exemple, après l'ajout, la modification ou la suppression de texte, vous voulez parfois annuler vos changements (mais toutefois les faire plus tard). À niveau simple, ce problème est souvent résolu en cliquant undo ou précédent dans notre éditeur de texte (annuler notre action précédente).

Une méthode plus naïve pour gérer nos différents changements est l'usage de plusieurs fichiers pour chaque version, et ce, simplement en créant des copies du fichier avec différents noms et changements (Important_Document_V4_FINAL_FINAL.doc vous semble malheureusement peut-être familier). À un niveau plus avancé, vous voulez souvent partager ces fichiers avec d'autres personnes, plutôt que de simplement faire et défaire des changements, revoir vos échanges par courriel pour savoir qui a changé quoi, pourquoi, quand, quel était son but, quel était le changement, pour pouvoir conserver des versions différentes du document en parallèle, un système de gestion de version (comme Git) vous permettra d'effectuer toutes ces opérations et bien plus!

Un système de contrôle de version peut donc résoudre tous vos problèmes de révision de versions et de retour en arrière en permettant l'utilisation multiple d'un même fichier sans le dupliquer. Il permet aussi la collaboration de ce même fichier par plusieurs personnes. Pour ces raisons, plusieurs organisations et entreprises utilisent un système de gestion de versions dans le but de garder la trace des différents changements dans le code source et les autres fichiers textes durant le développement d'un logiciel. Ces systèmes ont une grande quantité de fonctionnalités allant de la sauvegarde, la mise à jour et la conservation de traces de tout changement effectué.

Il y a deux modèles (types) de logiciel de contrôle de version : le Client-Server model et le Distributed model.

  • Client-Server model: Les développeurs utilisent un seul dossier qu'ils partagent. Quelques exemples:
    • Open source: CVS, Subversion, Vesta, etc.
    • Propriétaire: Microsoft Team Founday, Helix, etc.
  • Distributed mode: Chaque développeur travaille directement et localement avec son dossier et les changements sont échangés entre leurs dossiers uniquement lorsque demandé. Par exemple :
    • Open source: Git, SVK, Fossil, etc.
    • Propriétaire: Visual Studio Team Services, Plastic SCM, etc.

Vous avez peut-être appris à utiliser certains de ces systèmes de contrôle de version, mais pour cette section, nous nous concentrerons sur le système de contrôle de versions Git.

Git est le choix souvent le plus populaire (à apprendre et à utiliser), car il s'agit de code source ouvert, est facile à apprendre, ne prend quasiment aucun espace mémoire et est des plus performant côté rapidité. Il surclasse plusieurs ds autres outils avec ses fonctionnalités.

Utiliser un système de contrôle de version est souvent bien utile lorsque vous travaillez sur un projet en équipe, où encore lorsque vous avez l'option de partager publiquement votre projet (tel qu'en partageant un lien sur votre profil LinkedIn. Cela rend la tâche plus facile pour les compagnies qui cherchent à vous engager et qui désirent voir de quelle manière vous résolvez des problèmes et votre manière de coder, et ce, en se basant sur votre historique de projet. De plus, une connaissance de tels systèmes est définitivement un plus que les compagnies recherchent lorsqu'elles engagent des étudiants.

Introduction à Git

Git est un système de contrôle de version qui vous permet d'enregistrer tout changement à votre code ainsi que votre collaboration à celui d'autrui. Un Git Repository est en d'autres mots un dossier géré par Git où tous les changements au contenu sont enregistrés. Après avoir installé Git, vous pouvez transformer tous vos dossiers en Git Repository en tapant la commande suivante:

git init

La meilleure façon d'illustrer Git est l'enregistrement d'une capture d'écran instantanée de votre code.

  1. Vous faites des changements à vos fichiers.
  2. Vous sélectionnez les fichiers que vous voulez placer dans votre prochaine capture.
  3. Vous créez cette capture avec un message de description. Nous appelons ces captures des commits.

Git Local

Disons que nous avons un dossier contenant des fichiers sur notre ordinateur local dans « my_folder ».

  • index.html
  • about.html
  • home.html
  • contact.html
  • style.css
  • main.js
  • README.txt

Et disons que nous effectuons des changements dans des fichiers de ce « my_folder » ...

  • index.html
  • about.html
  • home.html
  • contact.html
  • style.css
  • main.js
  • README.txt

Ainsi, la suite d'actions typiques pour commettre ces changements dans Git tel qu'illustré à la Figure 1 serait:

  1. Faire des changements
  2. git status
  3. git add <files>
  4. git commit -m “Message”

Note: la commande "git status" affiche l'état de votre dossier auquel vous travaillez actuellement ainsi que les fichiers qui seront ajoutés à votre « commit ». Avant d'ajouter et de commettre ces changements, il est préférable de vérifier qu'est-ce que votre « commit » inclu et exclu.

AStuce: "git add ." est une commande commune pour ajouter tous les fichiers modifiés à ceux inclus dans le « commit ».

Typical Workflow.

Figure 1 : Typical Workflow.

Git Remote

Après un certain temps, vous vous retrouverez avec plusieurs captures et « commit ». Comment les partager avec vos coéquipiers? Avec Git Remote, vous vous mettez d'accord sur un endroit central où vous synchroniserez vos dossiers. Ensuite, vos coéquipiers peuvent aussi synchroniser leurs dossiers et fichiers dans cet endroit central que l'on appelle un “Git Remote Repository”.

Les Remote Repositories (dossiers à distance) sont uniquement des Git Repositories avec lesquels vous synchroniser vos données. Après chaque synchronisation, votre dossier local (local repository) et le dossier à distance (remote repository) contiene exactement les mêmes informations (toutes les captures, commits, etc.). Vous pouvez choisir n'importe quel endroit pour votre Git Remote repository, mais nous utiliserons un service appelé GitHub pour héberger notre dossier git à distance, tel qu'illustré dans la Figure 2.

GitHub Remote Repository.

Figure 2 : GitHub Remote Repository.

Pour débuter la synchronisation avec un Remote repository, vous devez

  1. Créer un Remote Repository sur Github.
  2. Ajouter son adresse à votre propre ordinateur (local)
git add remote <name> <git address>

Par exemple:

git add remote origin git@github.com:myusername/myRepoName.git

git push

Comment synchroniser votre dossier local avec celui à distance? D'abord vous pouvez poussez (push) vous changement au dossier à distance.

push <name of remote> <name of branch>
Par exemple:
git push origin master

git pull

Vous pouvez obtenir (pull) les changements les plus récents au dossier à distance en utilisant :

git pull

Vos coéquipers peuvent aussi obtenir les dernières versions en utilisant ces commandes. Il est recommandé d'utiliser git pull en premier pour obtenr les derniers changments, avant d'utiliser git push.

Méthode recommandé pour une pratique personnelle :

  1. Installez Git (https://git-scm.com/downloads)
  2. Essayez Git localement sur votre ordinateur
  3. Créez vous un compte GitHub (https://github.com/) (Utilisez votre adresse courriel étudiant pour obtenir gratuitement la version avancée!)

    ATTENTION: GitHub utilise des dossiers privés et publics. Si vous travaillez sur un devoir, assurez-vous que le dossier est PRIVÉ pour éviter de mauvaises surprises!
  4. Mettez en place un dossier à distance personnel (a personal remote repository) sur GitHub
  5. Pratiquez-vous à pousser (push) et obtenir (pull) de l'information

Références

Introduction à Git provient des notes de Casey Li slides. Pour davantage d'information sur GIT, nous recommandons fortement le vidéo suivant : "Gitting to Know You".

Quatrième partie

Quiz (1 point)

Pour l’implémentation de l’interface List à l’aide d’un tableau, ArrayList.

  1. Les insersions aux positions intermédiaires de la liste sont toujours rapides.
  2. L’ajout au début de la liste est toujours rapide.
  3. Le retrait d’un élément est toujours rapide.
  4. Consulter les positions intermédiaires de la liste est toujours rapide.

Inscrivez votre réponse à la question ci-dessus dans le champ Soumission : de la page de soumission du devor (voir ci-dessous) ;

  • https://uottawa.blackboard.com/
  •  

    Table of Contents