Première partie

Itérateurs

Pour ce laboratoire, vous utiliserez une liste chaînée afin de sauvegarder un nombre illimité de bits : des zéros et des uns. Contrairement aux implémentations vues jusqu’ici, les valeurs à l’intérieur des noeuds sont des entiers (int).

La classe BitList possède une classe interne. Il s'agit en fait d'une seconde définition de classe dont la visibilité est private se trouvant dans le même fichier de définition de la classe public BitList. Cette classe interne (inner en anglais) est BitListIterator.

BitListIterator réalise l'interface Iterator qui oblige l'implémentation de 3 méthodes, soit hasNext, next et add.

Prenez le temps de bien comprendre le comportement de chacune des méthodes et leur implémentation.

• Iterator.java
• BitList.java
• BitListMain.java

BitList

Puisque plusieurs opérations sur les bits nécessitent un traitement de droite à gauche, l’implémentation doit sauvegarder les bits dans l’ordre «droite à gauche», c.-à-d. le bit le plus à droite dans le mot binaire sera en en première position dans la liste (premier noeud).

Par exemple, les bits «11010» doivent être sauvegardés dans une liste telle que le premier noeud contienne 0, le second 1, suivi d’un 0, puis 1, et 1 :

• -> 0 -> 1 -> 0 -> 1 -> 1

1. Complétez l’implémentation de la classe BitList.

public BitList( String s ) 

Ce constructeur doit créer une liste représentant la chaîne de 0s et 1s donnée en entrée.

La chaîne s doit contenir que des 0s et des 1s sinon il faudra lancer l'exception IllegalArgumentException.

Le constructeur initialise cette nouvelle liste de bits afin de représenter la valeur de la chaîne. Chaque caractère de la chaîne représente un bit de la liste.

Par exemple, étant donné la chaîne «1010111», le constructeur doit initialiser cette liste afin d’y inclure les bits suivants (portez attention à l'ordre des bits encore une fois!).

• -> 1 -> 1 -> 1 -> 0 -> 1 -> 0 -> 1

Si la chaîne est vide, le constructeur doit créer une liste vide — la valeur null n’est pas valide.

Le constructeur ne doit pas retirer les zéros de la partie gauche. Par exemple, étant donné «0001» le constructeur doit initialiser cette liste comme suit.

• -> 1 -> 0 -> 0 -> 0

 

Deuxième partie

Iterative

Créez une classe nommée Iterative. Implémentez les méthodes ci-bas dans cette classe. Vos solutions doivent être itératives (c.-à-d. utilise des itérateurs).

Fichiers:

• Iterative.java
• IterativeMain.java

2.1 static BitList complement(BitList in)

Créez une méthode «static» itérative retournant une nouvelle liste de bits (BitList) qui soit le complément de celle en entrée. Le complément de 0 est 1 ; et vice-versa. Le complément d’une liste de bits est une nouvelle liste, de même longueur que l’entrée, telle que chaque bit est le complément du bit à la même position dans la liste d’entrée. Voici 4 exemples.

2.2 static BitList or(BitList a, BitList b)

Vous devez écrire une méthode de classe retournant le ou («or») des deux listes passées en paramètre. Cette liste a la même longueur que les listes en entrée et chacun des bits de cette liste est le ou («or») des bits à cette position dans les listes en entrée. La méthode lance une exception, IllegalArgumentException, si l’une ou l’autre des deux listes est vide ou si les listes sont de longueur différente.

Lorsque l’on compare deux bits avec le ou, le résultat est 1 si au moins l’un des bit est un 1, 0 si les deux bits sont des 0.

2.3 et et ou exclusif

Créer les méthodes static BitList and(BitList a, BitList b) et static BitList xor(BitList a, BitList b). Ces méthodes sont similaires à la méthode or mais il implémente respectivement le et binaire ainsi que le ou exclusif (xor).

Avec le et binaire, le résultat d’une comparaison est 1 si les deux bits sont 1, sinon le résultat est 0.

Avec le ou exclusif binaire, le résultat d’une comparaison est 1 si et seulement si l’un des deux bits est 1. Donc si les deux bits sont 0 ou 1, le résultat sera 0.

 

Troisième partie (optionnelle)

Cette partie est optionnelle et ne doit pas être remise. Cependant, nous vous le recommandons fortement, car il s'agit d'une excellente pratique pour l'examen final.

Pour cette partie du laboratoire, vous devez utiliser la classe BinarySearchTree.

Fichiers

• BinarySearchTree.java
• BinarySearchTreeTest.java

Vous devez implémenter les méthodes qui suivent.

1. E max()

Retourne la plus grande valeur de cet arbre. Lance l’exception NoSuchElementException si l’arbre est vide.

Par exemple, si vous déclarez BinarySearchTree t, et ajoute un animal "Lion" à l'arbre

BinarySearchTree t;
t = new BinarySearchTree();
t.add( "Lion" );

et appelez t.max(), cela devrait retourner "Lion".

2. E min()

Retourne la plus petite valeur de cet arbre. Lance l’exception NoSuchElementException si l’arbre est vide.

Par exemple, si vous appelez t.min() sur la base de l'exemple ci-dessus, cela devrait retourner "Lion".

3. int depth()

Retourne la profondeur de l’arbre, c’est-à-dire la profondeur du noeud le plus profond.

Par exemple, si vous appelez t.depth() sur la base de l'exemple ci-dessus, cela devrait retourner 0.

4. boolean isTwoTree()

Un arbre binaire est un two-tree s’il est vide ou si tous ses noeuds internes ont deux fils.

Par exemple, si vous appelez t.isTwoTree() sur la base de l'exemple ci-dessus, cela devrait retourner true.

 

Quatrième partie

Créer et soumettre un fichier zip (1 point)

Directives

• Créez un répertoire que vous nommerez lab11_123456, où vous remplacerez 123456 par votre numéro d'étudiant. Notez que le nom du répertoire est en minuscules, incluant la lettre «l».
• Dans ce répertoire, placer les fichiers pour les exercices du laboratoire. N'y ajoutez que le code source, les fichiers .java. En particulier, ne soumettez pas les fichiers .class.
• Dans ce répertoire, créez aussi un fichier texte nommé README.txt, qui devra contenir votre nom, numéro d'étudiant, ainsi qu'une brève description du contenu (en français ou en anglais, c'est votre choix) :

  
  Nom de l'étudiante ou de l'étudiant: Paidge Beaulieu
  Numéro d'étudiant: 123456
  Code du cours: ITI1521
  Section de laboratoire: A02
  
  Cette archive contient les 4 fichiers du laboratoire 11.
  
  Spécifiquement, ce fichier (README.txt), ainsi que
  Iterator.java, BitList.java, Iterative.java.
  
  						

• Créez un fichier zip lab11_123456.zip à partir du répertoire lab11_123456.
• Assurez-vous que cette archive comprend tous les fichiers nécessaires. Pour ce faire, copiez le fichier zip quelque part, ouvrez-le et assurez-vous que les fichiers et les répertoires espérés s'y trouvent.
• Soumettez l'archive sur le site Web https://uottawa.brightspace.com/.

Remarques importantes!

Nous utilisons des scripts automatisés pour tester et évaluer votre soumission de laboratoire. Par conséquent, vous devez suivre ces instructions à la lettre. En particulier:

• Les noms de tous les fichiers et méthodes doivent être exacts. Utilisez le code de démarrage fourni pour éviter des problèmes.
• Il faut soumettre un fichier .zip; pas de fichiers individuels; pas un .rar, pas un .7z, ni rien d’autre.
• Tous les fichiers de java doivent être présents et compiler avec succès (autrement dit, l’exécution de javac *.java ne doit générer aucune erreur), même si vous n’êtes pas capable de compléter un exercice.
• Notez si le code ne sera pas compilé en raison d'erreurs de syntaxe, vous n'obtiendrez pas de marque. Même si vous ne pouvez pas à résoudre complètement cet exercice, vous devez déposer un fichier contenant les méthodes intactes qui compilent correctement (vous pouvez mettre "return 0" si vous avez abandonné).
• Votre travail doit être soumis au plus tard à 23h30 le mardi de la semaine prochaine.

JUnits

Pour vous assurer que votre code est correct, nous avons préparé quelques tests unitaires.

Resources

• https://docs.oracle.com/javase/tutorial/getStarted/application/index.html
• https://docs.oracle.com/javase/tutorial/getStarted/cupojava/win32.html
• https://docs.oracle.com/javase/tutorial/getStarted/cupojava/unix.html
• https://docs.oracle.com/javase/tutorial/getStarted/problems/index.html