420-SF2-RE – Structures de données et programmation orientée objet

Pour ListeSimple, on avait :

class ListeVideException : Exception;
internal class ListeSimple : IEnumerable<int>
{
   class Noeud
   {
      public int Val { get; init; }
      public Noeud Succ { get; set; } = null;
      public Noeud (int val)
      {
         Val = val;
      }
   }
   Noeud Tête { get; set; } = null;
   Noeud Queue { get; set; } = null;
   public bool EstVide => Tête == null;
   // complexité : O(1)
   public void AjouterDébut(int val)
   {
      Noeud p = new(val);
      if (EstVide)
         Queue = p;
      p.Succ = Tête;
      Tête = p;
      ++Count;
   }
   // note : privée
   // précondition : !EstVide
   // complexité : O(n)
   Noeud TrouverDernier()
   {
      Noeud p = Tête;
      for (; p.Succ != null; p = p.Succ)
         ;
      return p;
   }
   // complexité : O(1) :)
   public void AjouterFin(int val)
   {
      if(EstVide)
         AjouterDébut (val);
      else
      {
         Noeud p = new(val);
         Noeud q = Queue;
         q.Succ = p;
         Queue = p;
         ++Count;
      }
   }
   // complexité : O(1)
   public void SupprimerDébut()
   {
      if (EstVide)
         throw new ListeVideException();
      Tête = Tête.Succ;
      if (EstVide)
         Queue = null;
      --Count;
   }
   public int Count { get; private set; } = 0;
   // complexité : O(1)
   public int PeekDébut()
   {
      if (EstVide)
         throw new ListeVideException();
      return Tête.Val;
   }
   // complexité : O(n)
   public int PeekFin()
   {
      if (EstVide)
         throw new ListeVideException();
      return TrouverDernier().Val;
   }
   // TEMPORAIRE ARK ARK ARK
   //public void Afficher()
   //{
   //   for (Noeud p = Tête; p != null; p = p.Succ)
   //      Console.Write($"{p.Val} ");
   //   Console.WriteLine();
   //}
   // duplication (version méthode d'instance)
   // complexité : O(n)... :)
   public ListeSimple Dupliquer()
   {
      ListeSimple lst = new();
      for(Noeud p = Tête; p != null; p = p.Succ)
         lst.AjouterFin(p.Val);
      return lst;
   }
   public IEnumerator<int> GetEnumerator() => // :)
      new Énumérateur(this);
   IEnumerator IEnumerable.GetEnumerator() => // relique du passé
      new Énumérateur(this);
   class Énumérateur : IEnumerator<int>
   {
      Noeud Cur { get; set; }
      public Énumérateur(ListeSimple src)
      {
         Cur = new(0); // 0 : bof
         Cur.Succ = src.Tête;
      }
      public int Current => Cur.Val;
      object IEnumerator.Current => Cur.Val;
      public void Dispose() { }
      public bool MoveNext()
      {
         // si je ne peux plus progresser : faux
         if(Cur.Succ == null)
            return false;
         // sinon, je progresse, puis vrai
         Cur = Cur.Succ;
         return true;
      }
      public void Reset() { }
   }
   // duplication (version méthode de classe)
   //public static ListeSimple Dupliquer(ListeSimple src)
   //{
   //   ListeSimple lst = new();
   //   for (Noeud p = src.Tête; p != null; p = p.Succ)
   //      lst.AjouterFin(p.Val);
   //   return lst;
   //}
}

Pour ListeDouble<T>, on avait :

internal class ListeDouble<T> : IEnumerable<T>
   where T : IEquatable<T> 
{
   class Noeud
   {
      public T Val { get; init; }
      public Noeud Succ { get; set; } = null;
      public Noeud Pred { get; set; } = null;
      public Noeud(T val)
      {
         Val = val;
      }
   }
   public int Count { get; private set; } = 0;
   Noeud Tête { get; set; } = null;
   Noeud Queue { get; set; } = null;
   public bool EstVide => Count == 0;
   // AjouterDébut
   public void AjouterDébut(T val)
   {
      Noeud p = new(val);
      if (EstVide)
         Tête = Queue = p;
      else
      {
         Tête.Pred = p;
         p.Succ = Tête;
         Tête = p;
      }
      ++Count;
   }
   // AjouterFin
   public void AjouterFin(T val)
   {
      Noeud p = new(val);
      if (EstVide)
         Tête = Queue = p;
      else
      {
         Queue.Succ = p;
         p.Pred = Queue;
         Queue = p;
      }
      ++Count;
   }
   // SupprimerDébut
   public void SupprimerDébut()
   {
      if (EstVide)
         throw new ListeVideException();
      Tête = Tête.Succ;
      if (Tête == null)
         Queue = null;
      else
         Tête.Pred = null;
      --Count;
   }
   // SupprimerFin
   public void SupprimerFin()
   {
      if (EstVide)
         throw new ListeVideException();
      Queue = Queue.Pred;
      if (Queue == null)
         Tête = null;
      else
         Queue.Succ = null;
      --Count;
   }
   // PeekDébut
   public T PeekDébut()
   {
      if (EstVide)
         throw new ListeVideException();
      return Tête.Val;
   }
   // PeekFin
   public T PeekFin()
   {
      if (EstVide)
         throw new ListeVideException();
      return Queue.Val;
   }
   // Dupliquer
   public ListeDouble<T> Dupliquer()
   {
      ListeDouble<T> lst = new();
      for (Noeud p = Tête; p != null; p = p.Succ)
         lst.AjouterFin(p.Val);
      return lst;
   }
   // ARK ARK ARK
   //public void Afficher()
   //{
   //   for (Noeud p = Tête; p != null; p = p.Succ)
   //      Console.Write($"{p.Val} ");
   //   Console.WriteLine();
   //}
   // Contient : retourne true seulement si la liste
   //            contient une valeur donnée
   // complexité : O(n)
   public bool Contient(T val) => Trouver(val) != null;
   //{
   //   for(Noeud p = Tête; p != null; p = p.Succ)
   //      if(p.Val.Equals(val)/*p.Val == val*/)
   //         return true;
   //   return false;
   //}
   // Compter : retourne le nombre d'occurrences d'une
   //           valeur donnée dans la liste
   // complexité : O(n)
   public int Compter(T val)
   {
      int n = 0;
      for (Noeud p = Tête; p != null; p = p.Succ)
         if (p.Val.Equals(val)/*p.Val == val*/)
            ++n;
      return n;
   }
   // Supprimer : supprimer la première occurrence
   //             d'une valeur dans la liste
   public void Supprimer(T val)
   {
      Noeud p = Trouver(val);
      // ici, soit p est null, soit p.Val vaut val
      if(p != null)
      {
         if (p.Succ == null) // dernier noeud
            Queue = p.Pred;
         else
            p.Succ.Pred = p.Pred;
         if (p.Pred == null) // premier noeud
            Tête = p.Succ;
         else
            p.Pred.Succ = p.Succ;
         --Count;
      }
   }
   // (privée) Trouver : retourne une référence sur
   //          la première occurrence d'un noeud d'une
   //          valeur donnée, null sinon
   Noeud Trouver(T val)
   {
      for (Noeud p = Tête; p != null; p = p.Succ)
         if (p.Val.Equals(val)/*p.Val == val*/)
            return p;
      return null;
   }
   public IEnumerator<T> GetEnumerator() =>
      new Énumérateur(this);
   IEnumerator IEnumerable.GetEnumerator() =>
      new Énumérateur(this);
   class Énumérateur : IEnumerator<T>
   {
      Noeud Cur { get; set; }
      public Énumérateur(ListeDouble<T> src)
      {
         Cur = new(default) ;
         Cur.Succ = src.Tête;
      }
      public T Current => Cur.Val;
      object IEnumerator.Current => Cur.Val;
      public void Dispose() { }
      public bool MoveNext()
      {
         if (Cur.Succ == null)
            return false;
         Cur = Cur.Succ;
         return true;
      }
      public void Reset() { }
   }
}

Pour Tableau<T>, on avait :

internal class Tableau<T> : IEnumerable<T>
   where T : IEquatable<T>, IComparable<T>
{
   T[] Substrat { get; set; }
   public int Count { get; private set; }
   // invariant : Substrat != null
   public int Capacity => Substrat.Length;
   public bool EstVide => Count == 0;
   public bool EstPlein => Count == Capacity;
   // modélise un Tableau vide
   // complexité : O(1) (constante)
   public Tableau()
   {
      Substrat = new T[0];
      Count = 0;
   }
   // modélise un ajout d'une valeur à la fin du Tableau
   // complexité : O(1) amortie
   //              - constante d'habitude
   //              - linéraire à l'occasion (malchance)
   public void Add(T val)
   {
      if (EstPlein)
         Croître();
      Substrat[Count] = val;
      ++Count;
   }
   // accroît la capacité du substrat
   // complexité : O(n) (linéaire)
   void Croître()
   {
      int nouvCap = Capacity == 0 ? 8 : Capacity * 2;
      T[] tab = new T[nouvCap];
      for(int i = 0; i != Count; ++i)
         tab[i] = Substrat[i];
      Substrat = tab;
   }
   // TEMPORAIRE (ark ark ark)
   //public void Afficher()
   //{
   //   for(int i = 0; i != Count; ++i)
   //      Console.Write($"{Substrat[i]} ");
   //   Console.WriteLine();
   //}
   // complexité : O(n)
   public void InsertAt(int indice, T val)
   {
      if (indice < 0 || Count <= indice)
         throw new IndexOutOfRangeException();
      if (EstPlein)
         Croître();
      for (int i = Count - 1; i >= indice; --i)
         Substrat[i + 1] = Substrat[i];
      Substrat[indice] = val;
      ++Count;
   }
   // complexité : O(n)
   public void RemoveAt(int indice)
   {
      if (indice < 0 || Count <= indice)
         throw new IndexOutOfRangeException();
      for (int i = indice + 1; i < Count; ++i)
         Substrat[i - 1] = Substrat[i];
      --Count;
   }
   // trouve la première occurrence de val dans substrat
   // complexité : O(n)
   int TrouverPremièreOccurrence(T val)
   {
      for(int i = 0; i != Count; ++i)
         if(Substrat[i].Equals(val))
            return i;
      return -1;
   }
   // complexité : O(n)
   public void Remove(T val)
   {
      int indice = TrouverPremièreOccurrence(val);
      RemoveAt(indice);
   }
   // complexité : O(n^2) (quadratique)
   public void Trier() // tri à bulles : ne faites pas ça...!
   {
      for(int i = 0; i < Count - 1; ++i) // main gauche
         for(int j = i + 1; j < Count; ++j) // main droite
            if(!(Substrat[i].CompareTo(Substrat[j]) <0))
            {
               T temp = Substrat[i];
               Substrat[i] = Substrat[j];
               Substrat[j] = temp;
            }
   }
   public IEnumerator<T> GetEnumerator() =>
      new Énumérateur(this);
   IEnumerator IEnumerable.GetEnumerator() =>
      new Énumérateur(this);
   class Énumérateur : IEnumerator<T>
   {
      Tableau<T> Src { get; init; }
      int Indice { get; set; } = -1;
      public Énumérateur(Tableau<T> src)
      {
         Src = src;
      }
      public T Current => Src[Indice];
      object IEnumerator.Current => Src[Indice];
      public bool MoveNext()
      {
         // si je ne peux pas avancer : faux
         if (Indice == Src.Count - 1)
            return false;
         // sinon, j'avance puis vrai
         ++Indice;
         return true;
      }
      public void Reset() { }
      public void Dispose() { }
   }
   // en attendant mieux...
   //public T GetÉlément(int indice) => Substrat[indice];
   public T this[int indice]
   {
      get => Substrat[indice];
      set { Substrat[indice] = value; }
   }
}

Allo!

On a eu la gentillesse de me demander quelques exercices pour pratiquer en vue de la PFI et de l'examen final cette semaine. Les quatre sujets suivants m'ont été mentionnés (je peux en ajouter, mais le temps file alors essayez de m'avertir rapidement si vous voulez quelque chose... et essayez d'être spécifiques!)

Sujet 0 : Encapsulation et conception de classes

Question : dans quelle situation devrait-on utiliser set?

Réponse : quand la propriété est modifiable pendant la vie de l'objet. Par exemple :

class Voiture
{
   // ...
   public int Kilométrage{ get; private set; }; // ← peut changer quand la voiture se déplace, donc set
   // ...
   public Voiture()
   {
      // ...
      Kilométrage = 0; // kilométrage initial
      // ...
   }
   public void Avancer(int nbMètres)
   {
      Kilométrage += nbMètres / 1000; // grossière approximation, juste pour illustrer le propos
   }
   // ...
}

Dans quelle situation devrait-on utiliser init?

Réponse : quand la propriété est n'est plus modifiable une fois l'objet construit. Par exemple :

class Voiture
{
   // ...
   public string Marque{ get; private init; }; // ← fixé pour la vie de la voiture
   // ...
   public Voiture(string marque)
   {
      // ...
      Marque = marque; // ça fait « partie de son ADN » désormais :)
      // ...
   }
   // ...
}

Question : comment choisir entre set et init?

Réponse : un bon truc à retenir est que, dans un langage comme C# où les classes sont des « types références » donc où les référés sont partagés jusqu'à preuve du contraire, tout ce qui est modifiable demande de la prudence. Ainsi, c'est probablement mieux de préférer init si possible, et d'utiliser set si nécessaire. Ça évite des surprises comme :

class Point
{
   public int X { get; set; } // ← set semble innocent ici, mais...
   public int Y { get; set; }
   public Point() : this(0,0) {}
   public Point(int x, int y)
   {
      X = x;
      Y = y;
   }
}
class Cercle
{
   public float Rayon{ get; init; }
   public Point Centre { get; init; } // ← note : init, mais Point n'est pas immuable
   // supposons qu'on tienne à ce que Centre soit dans le premier quadrant
   static bool EstAcceptable(Point p) => p.X >=0 && p.Y >= 0;
   public Cercle(float rayon, Point centre)
   {
      Rayon = rayon;
      Centre = EstAcceptable(centre) ? centre : throw new ArgumentException();
   }
}
// ...
// on arrive au code client

Point pt = new(); // 0,0
Cercle c = new(1.0f, pt); // Ok, pt est dans le premier quadrant
pt.X = -15; // OUPS! pt est partagé par c et par le code client...
            // un nvariant de c vient d'être brisé

Question : comment identifier les préconditions, postconditions et les invariants dans un programme existant?

Réponse : il n'y a pas de réponse universelles à celle-là, mais si le code est bien écrit, on a quelques indices :

Les constructeurs, les set et les init qui font de la validation tendent à nous dire quelles sont les conditions de validité de la classe, donc à décrire les invariants. Évidemment, si on éparpille la validation partout, c'est plus difficile à voir
Les préconditions sont les trucs que la fonction appelée tient pour acquis. Par exemple :
- si une fonction accepte un indice en paramètre et l'utilise aveuglément pour accéder un tableau, alors une précondition de cette fonction est que cet indice soit valide
- si une fonction accepte une référence sur un objet et s'en sert sans valider qu'il soit non-nul, alors c'est une précondition de cette fonction qu'il soit non-nul
- si une fonction validant si un paramètre est entre deux bornes min et max se sert de min et max sans s'assurer que min<=max au préalable, alors il s'agit d'une de ses préconditions
Les postconditions sont les effets que garantit la fonction appelée, dans la mesure où les préconditions sont respectées bien sûr. Par exemple, dans le code de la classe Tableau<T> faite en classe, les postconditions de Add sont :
- dans le cas d'un succès sont (a) que l'élément à ajouter soit bien ajouté à la fin du substrat, (b) que le Count ait incrémenté de un, et (c) que la Capacité après le Add soit au moins aussi grande qu'elle ne l'était avant le Add
- dans le cas d'un échec, (a) que l'élément à ajouter ne sont pas ajouté, (b) que le Count demeure inchangé, (c) que la Capacité demeure inchangée, et (d) qu'une exception soit levée pour rapporter la raison de l'insuccès (probablement un manque de mémoire lors du new)

Dans du code bien écrit, les préconditions, postconditions et, dans le cas des classes, les invariants devraient être clairement identifiés, au moins dans des commentaires. C'est pas toujours aussi clair dans le cas d'une évaluation à l'école, je vous l'accorde.

Sujet 1 : Surchage d'opérateurs

Question : comment lire (et comprendre) un message d'erreur lorsque le programme ne compile pas?

Réponse : c'est difficile de répondre à ceci parce qu'il y a beaucoup de cas de figure selon les erreurs!

Essayons une réponse avec un exemple simple. Voici la version correcte, qui compile et affiche la bonne valeur (https://dotnetfiddle.net/rVwi7V) :

using System;

X a = new(3), b = new(2);
X c = a + b;
Console.Write(c);

class X
{
   int Val{ get; init; }
   public X (int val) { Val = val; }
   public static X operator+(X x0, X x1) => new(x0.Val + x1.Val); // ← ici
   public override string ToString() => $"{Val}";
}

Quelles sont les erreurs possibles? Essayons quelques options (note : j'utilise .NET Fiddle ici alors les messages d'erreurs sont en anglais, mais ils me semblent lisibles tout de même) :

Oublier le mot public (https://dotnetfiddle.net/jMki22). Le message d'erreur est « Compilation error (line 11, col 30): User-defined operator 'X.operator +(X, X)' must be declared static and public ».
Oublier le mot static (https://dotnetfiddle.net/lCnrje). Le message d'erreur est encore une fois « Compilation error (line 11, col 30): User-defined operator 'X.operator +(X, X)' must be declared static and public ».
L'écrire de manière plus longue, avec accolades et return explicite, mais oublier le return (https://dotnetfiddle.net/wzhlXA). Le message d'erreur est « Compilation error (line 11, col 26): 'X.operator +(X, X)': not all code paths return a value ».
Essayer de retourner un int plutôt qu'un X (https://dotnetfiddle.net/gefGft). Le message d'erreur est « Compilation error (line 11, col 43): Cannot implicitly convert type 'int' to 'X' ».
On pourrait aussi oublier un paramètre, mais faites attention car l'opérateur + unaire (à un seul opérande) existe et est légal, tout comme l'est l'opérateur - unaire que nous avons utilisé à quelques reprises.

Les messages me semble plutôt clairs (ça dit la ligne, la colonne, et la raison précise du problème dans chaque cas). Faut surtout les lire avec attention.

Sujet 2 : Héritage et polymorphisme

Question : comment les manipuler, en profiter, écrire du code qui en tient compte?

Réponse : il y a ../../../Sujets/Divers--cdiese/Polymorphisme.html qui est très détaillé, mais pour une idée plus simple... Imaginez tout cas où (a) il y a le verbe « être » qui intervient dans la relation, (b) il y a au moins un comportement commun à plusieurs classes, et (c) il y a des variations dans les manières d'implémenter ce comportement...

Par exemple, vous avez des clowns dans un cirque. Tout clown fait des grimaces, et par défaut ça fait le son "Blah" :

class Clown
{
   public string Nom{ get; init; }
   public Clown(string nom) { Nom = nom; }
   public virtual string Grimace() => "Blah";
}

Toutefois, il y a des clowns plus spécialisés. Par exemple, un clown triste qui, dans ses grimaces, fait "Bouhouhou" :

class ClownTriste : Clown
{
   public ClownTriste(string nom) : base(nom) { }
   public override string Grimace() => "Bouhouhou";
}

... et des clowns qui font un peu plus peur :

class Pennywise : Clown
{
   public Pennywise(string nom) : base(nom) { }
   public override string Grimace() => "NYAHAHA!";
}

Armé de cette hiérarchie de clowns, on peut faire un programme... divertissant (https://dotnetfiddle.net/T8TUF6) :

using System;
using System.Collections.Generic;

foreach(var clown in CréerAmuseurs(10))
   AmuserAvec(clown);

static List<Clown> CréerAmuseurs(int n)
{
   List<Clown> lst = new();
   Random dé = new();
   for(int i = 0; i != n; ++i)
	   lst.Add((dé.Next() % 3) switch {
	      0 => new Clown($"Clown {n + 1}"),
		  1 => new ClownTriste($"Clown {n + 1}"),
		  2 => new Pennywise($"Clown {n + 1}"),
		  _ => null // impossible mais faut faire taire le compilateur
	   });
   return lst;
}

static void AmuserAvec(Clown c)
{
   Console.WriteLine($"{c.Nom} fait {c.Grimace()}");
}
// ...

Sujet 3 : Interface, encapsulation et code générique

Demande : un peu de pratique ne ferait pas de tort

Réponse : il y a quand même pas mal d'exercices aux séances S17, S18 et S19. Pour en ajouter quelques-uns :

EX00 – Écrivez la fonction générique Séparer<T> acceptant en paramètre un IEnumerable<T> et un prédicat applicable à un T, et retournant un uplet fait de deux List<T>. La première doit contenir les éléments de l'énumérable qui satisfont le prédicat, alors que la seconde doit contenir ceux qui ne satisfont pas le prédicat.

Par exemple, avec le code client suivant :

var (oui, non) = Séparer(new []{ 1,2,3,4,5 }, n => n % 2 == 0);

... la List<int> nommée oui contiendra 2,4 alors que la List<int> nommée non contiendra 1,3,5.

EX01 -- Écrivez la classe Ensemble<T> qui est telle que chacun de ses éléments est unique (il n'est égal à aucun autre). On aimerait que le code suivant :

Ensemble<int> e0 = new(), e1 = new();
foreach(int n in new[]{ 2,3,5,7,11 })
   e0.Add(n);
foreach(int n in new[]{ 2,3,3,5,7,11,5,2,3 })
   e1.Add(n);
Console.WriteLine(e0 == e1 ? "OUI" : "NON");
Console.WriteLine(e0.Count == 5 ? "OUI" : "NON");
Console.WriteLine(e1.Count == 9 ? "OUI" : "NON)";
Console.WriteLine(e1.Count == 5 ? "OUI" : "NON");

... compile et affiche "OUI", "OUI", "NON", "OUI" dans l'ordre.

	Je corrige les programmes en appliquant des codes de correction. Vous trouverez ici la liste des codes les plus fréquents.
	Ma stratégie de correction en tant que telle (pour le code, à tout le moins) est résumée ici.
	Cliquez sur cette cible pour un résumé des principales règles de programmatique en vigueur dans ce cours.
	Cliquez sur cette cible pour les normes appliquées dans ce cours, en ce qui a trait au pseudocode

Travail	Nom	Rôle
Labo 00	Le Cryptographe	Travail sur l'encapsulation et la conception de classes
Labo 01	À venir	Travail sur l'héritage et le polymorphisme
Labo 02	À venir	Travail sur les interfaces, l'encapsulation et le code générique
Labo 03	À venir	Travail sur les dictionnaires, les fonctions génériques et les entrées / sorties
PFI	Production finale d'intégration	À venir

420-SF2-RE – Structures de données et programmation orientée objet

Pratiques de correction

Détail des séances en classe

Petits coups de pouces

Travaux pratiques

Solutionnaires et exemples

Programme de test – S04 Exercice 1a

Programme de test – S04 Exercice 1b

Code vu en classe à la séance S05 pour l'exercice 3 de la séance S04

Classe Algos

Classe Personnage

Classe Héros

Classe Monstre

Code (complet cette fois) vu en classe à la séance S06 pour l'exercice 3 de la séance S04

Classe Algos

Classe Personnage

Classe Héros

Classe Monstre

Programme de test

Code vu en classe à la séance S06 pour l'exercice 4 de la séance S04

Classe Point

Classe Carré

Code de test

Code vu en classe lors de la séance S15

Classe Tableau

Classe Pile (version reposant sur un Tableau)

Classe Pile (version reposant sur des noeuds)

Activité de la séance S13

Classe Algos

Classe Arme

Classe Personnage

Classe Héros

Classe Monstre

Classe GroupePersos

Classe Armée

Classe Horde

Classe Program