|
13 mars |
S00 |
Au menu :
- Présentation du cours et du plan
de cours, du moins le volet qui nous concerne
- Nos thèmes pour ces trois séances seront (dans le désordre!) :
- Petit exercice de remise en forme :
- Implémentons une liste simplement chaînée d'éléments d'un certain
type T
- Comment la représenterons-nous?
- Quelle serait une bonne interface d'utilisation pour ce type?
- Quels sont les coûts des principales opérations associées à ce
type?
- Si vous souhaitez poursuivre le plaisir, à titre d'exercice
(répétez la réflexion de design dans chaque cas) :
- Transformez la liste simplement chaînée de T
en liste doublement chaînée de T
- Écrivez un TableauDynamique<T>
inspiré, dans son interface, par le (très mal nommé) type
List<T> de la
plateforme .NET
- Rappel sur :
L'activité de cette semaine vous sera présentée au cours de la séance.
- Présentation de l'activité pour cette semaine. Attention :
les activités sont cumulatives, alors ne prenez pas de retard!
- Cette semaine, votre activité sera (à venir)
boites-v0.html
- Notez que le code proposé est en C# 9. Vous pouvez le
« simplifier » (légèrement) avec une version plus récente du
langage.
L'exemple de Liste<T> fait en classe était :
using System;
using System.Collections;
using System.Collections.Generic;
namespace z
{
class ListeVideException : Exception;
internal class Liste<T>
: IEnumerable<T>
where T : IEquatable<T>
{
class Noeud
{
public T Valeur { get; init; }
public Noeud Succ { get; set; } = null;
public Noeud(T val)
{
Valeur = val;
}
}
Noeud Tête { get; set; } = null;
Noeud Queue { get; set; } = null;
// O(1) : constant
public bool EstVide => Tête == null;
// O(1) : constant
public void AjouterDébut(T val)
{
Noeud p = new(val);
if (EstVide)
Queue = p;
p.Succ = Tête;
Tête = p;
++Count;
}
// O(1) :)
public void AjouterFin(T val)
{
Noeud p = new(val);
if (EstVide)
Tête = Queue = p;
else
{
Queue.Succ = p;
Queue = p;
}
++Count;
}
// précondition : !EstVide
// O(n)
//Noeud TrouverDernier()
//{
// Noeud p = Tête;
// for (; p.Succ != null; p = p.Succ)
// ;
// return p;
//}
// O(1)
public void RetirerDébut()
{
if (EstVide)
throw new ListeVideException();
Tête = Tête.Succ;
if (EstVide)
Queue = null;
--Count;
}
// O(1)
public T ValeurPremier =>
EstVide ? throw new ListeVideException() : Tête.Valeur;
// O(1) :)
public T ValeurDernier =>
EstVide ? throw new ListeVideException() : Queue.Valeur;
public int Count { get; private set; } = 0;
// supprimer la première occurrence de val (si elle existe)
// O(n)
public void Retirer(T val)
{
if(!EstVide)
{
if (val.Equals(Tête.Valeur))
RetirerDébut();
else
{
for(Noeud p = Tête; p.Succ != null; p = p.Succ)
if(p.Succ.Valeur.Equals(val))
{
if(p.Succ.Succ == null)
Queue = p;
p.Succ = p.Succ.Succ;
--Count;
break;
}
}
}
}
// ARK ARK ARK FAUT PAS QUE ÇA RESTE LÀ
//public void Afficher()
//{
// for (Noeud p = Tête; p != null; p = p.Succ)
// Console.Write($"{p.Valeur} ");
//}
// O(n) :)
public static Liste<T> Dupliquer(Liste<T> lst)
{
Liste<T> nouvelleListe = new();
for (Noeud p = lst.Tête; p != null; p = p.Succ)
nouvelleListe.AjouterFin(p.Valeur);
return nouvelleListe;
}
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(Liste<T> src)
{
Cur = new(default);
Cur.Succ = src.Tête;
}
public T Current => Cur.Valeur;
object IEnumerator.Current => Cur.Valeur;
public bool MoveNext()
{
if (Cur.Succ == null)
return false;
Cur = Cur.Succ;
return true;
}
public void Reset() { }
public void Dispose() { }
}
}
}
Le code de test était :
using z;
Liste`<int> lst = new();
foreach (int n in new[] { 2, 3, 5, 7, 11 })
lst.AjouterDébut(n);
foreach (int n in new[] { -1, -2, -3 })
lst.AjouterFin(n);
Afficher(lst); // 11 7 5 3 2 -1 -2 -3
Console.WriteLine();
Console.WriteLine($"Premier : {lst.ValeurPremier} ; dernier : {lst.ValeurDernier}"); // Premier : 11 ; dernier : -3
lst.Retirer(2); // MEURS!!!!
Afficher(lst); // 11 7 5 3 -1 -2 -3
Console.WriteLine();
Liste<int> autreListe = Liste<int>.Dupliquer(lst); // lst;
while(!lst.EstVide)
{
lst.RetirerDébut();
Afficher(lst);
Console.WriteLine();
}
Console.WriteLine("Roulement de tambour...");
Afficher(autreListe);
static void Afficher<T>(Liste<T> lst) where T : IEquatable<T>
{
foreach (T e in lst)
Console.Write($"{e} ");
}
Pour un exemple d'énumérateurs sur des entiers pairs, voir
https://dotnetfiddle.net/EZ9jFR :
using System;
using System.Collections;
using System.Collections.Generic;
foreach (int n in new Pairs(1, 10))
Console.Write($"{n} "); // 2 4 6 8 10
class Pairs : IEnumerable<int>
{
int Min { get; init; }
int Max { get; init; }
public Pairs(int min, int max)
{
Min = min;
Max = max;
// valider que Min <= Max si vous voulez
}
class ÉnumPairs : IEnumerator<int>
{
int Cur { get; set; }
Pairs Source { get; init; }
public ÉnumPairs(Pairs source)
{
Source = source;
// en C# comme en Java, faut se placer avant le premier élément à parcourir
Cur = Source.Min % 2 == 0 ? Source.Min - 2 : Source.Min - 1;
}
public bool MoveNext()
{
if (Cur + 2 > Source.Max) return false;
Cur += 2;
return true;
}
public int Current => Cur;
object IEnumerator.Current => throw new NotImplementedException();
// Vous devez aussi coder quelques trucs sans intérêt, que vous pouvez faire générer par Visual Studio
public void Reset() { }
public void Dispose() { }
}
// GetEnumerator doit retourner un IEnumerable capable de parcourir les éléments de la séquence
public IEnumerator<int> GetEnumerator() => new ÉnumPairs(this);
// Vous devez aussi coder un autre truc sans intérêt, que vous pouvez faire générer par Visual Studio
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() =>
throw new NotImplementedException();
}
Pour l'exemple de Liste<T> avec énumérateur
(et un peu plus),
voir
https://dotnetfiddle.net/aK9oxz :
using System;
using System.Collections;
using System.Collections.Generic;
var lst = new Liste<string>();
lst.AjouterIntervalle(new []{ "J'aime", "mon", "prof" });
foreach (var s in lst)
Console.Write($"{s} ");
class ListeVideException : Exception { }
class Liste<T> : IEnumerable<T>
{
public IEnumerator<T> GetEnumerator() =>
new Énumérateur(Tête);
IEnumerator IEnumerable.GetEnumerator() =>
new Énumérateur(Tête);
// un énumérateur de C# / un itérateur de Java, modélise
// une séquence à demi ouverte (debut, fin]
class Énumérateur : IEnumerator<T>
{
Noeud Cur { get; set; }
public Énumérateur(Noeud tête)
{
Cur = new (default);
Cur.Succ = tête;
}
public bool MoveNext()
{
if (Cur.Succ == null)
return false;
Cur = Cur.Succ;
return true;
}
public void Reset() => throw new NotImplementedException();
public void Dispose() { }
public T Current => Cur.Valeur;
object IEnumerator.Current => Cur.Valeur;
}
class Noeud
{
public T Valeur { get; init; }
public Noeud Succ { get; set; } = null;
public Noeud(T val)
{
Valeur = val;
}
}
Noeud Tête { get; set; } = null;
Noeud Queue { get; set; } = null;
public bool EstVide => Tête == null;
public void AjouterDébut(T val)
{
var noeud = new Noeud(val);
if (EstVide)
Tête = Queue = noeud;
else
{
noeud.Succ = Tête;
Tête = noeud;
}
}
public void AjouterFin(T val)
{
Noeud noeud = new (val);
if (EstVide)
Tête = Queue = noeud;
else
{
Queue.Succ = noeud;
Queue = noeud;
}
}
public void SupprimerDébut()
{
if (EstVide)
throw new ListeVideException();
Tête = Tête.Succ;
if (Tête == null)
Queue = null;
}
public T PeekDébut() =>
EstVide? throw new ListeVideException(): Tête.Valeur;
public T PeekFin()
{
if (EstVide)
throw new ListeVideException();
return Queue.Valeur;
}
//public static Liste<T> Dupliquer(Liste<T> src)
//{
// Liste<T> dest = new();
// for (Noeud p = src.Tête; p != null; p = p.Succ)
// dest.AjouterFin(p.Valeur);
// return dest;
//}
public Liste<T> Dupliquer()
{
Liste<T> dest = new();
for (Noeud p = Tête; p != null; p = p.Succ)
dest.AjouterFin(p.Valeur);
return dest;
}
public void AjouterIntervalle(IEnumerable<T> src)
{
foreach(T e in src)
AjouterFin(e);
}
}
|
|
20 mars |
S01 |
Au menu :
- Questions à propos de
boites-v0.html (n'hésitez pas!)
- C'est normal de trouver cela difficile
- C'est un travail qui demande
de réfléchir et de chercher l'élégance, et qui « résiste » aux
« solutions » par force brute, qui fonctionnent en ajoutant du code et
du code... et qui ne sont pas de vraies solutions
- En même temps, réfléchir sur son code, ça fait grandir!
- Considérations techniques :
- Importance de pouvoir redimensionner un
IBoite (utilisez le nom pour l'idée équivalente dans votre
implémentation)
- Importance de cloner les IBoite
- À propos du rôle crucial des énumérateurs
- Schéma de conception
Fabrique
L'esquisse (incomplète et illustrative sans plus) de fabrique de boîtes
faite en classe était :
string s = "mono allo\nch\nmono yo\nch\nmono coucou\nmono bye";
static int TrouverSi(string s, int depuis, Func<char, bool> pred)
{
for (; depuis != s.Length && !pred(s[depuis]); ++depuis)
;
return depuis;
}
static (Sorte, int) FabriquerBoiteGenre(string s, int cur = 0)
{
int finPréfixe = TrouverSi(s, cur, c => c == ' ');
string préfixe = s.Substring(cur, finPréfixe - cur);
Console.WriteLine($"Préfixe trouvé : {préfixe}");
switch(préfixe)
{
case "mono":
{
int finLigne = TrouverSi(s, finPréfixe, c => c == '\n');
// le texte du monon est s.Substring(finPréfixe, finLigne - finPréfixe)
return (Sorte.Mono, finLigne + 1);
}
break;
case "ch":
{
int finLigne = TrouverSi(s, finPréfixe, c => c == '\n');
var (b0, fin0) = FabriquerBoiteGenre(s, finLigne + 1);
var (b1, fin1) = FabriquerBoiteGenre(s, fin0 + 1);
return (Sorte.CH, fin1 + 1);
}
break;
default:
throw new Exception("bof");
}
}
enum Sorte { Mono, CH } // etc.
Le code fait en exemple pour le
clonage était :
Image p = new Bmp(ConsoleColor.DarkBlue);
p.Dessiner();
p = ModifierPeutÊtre(p);
p.Dessiner();
p = new Jpeg(ConsoleColor.Red);
p.Dessiner();
p = ModifierPeutÊtre(p);
p.Dessiner();
static Image ModifierPeutÊtre(Image p)
{
// A) faire un backup de ce vers quoi p pointe
Image backup = p.Cloner();
// B) modifier l'image pointée par p
p.Couleur = ConsoleColor.Cyan;
// C) demander à l'usager s'il / si elle souhaite conserver les modifs7
Console.Write("Nouvelle image : ");
p.Dessiner();
Console.Write("Conserver les modifs? (o / n) ");
char c = char.Parse(Console.ReadLine());
// i) si oui, on retourne p
// ii) sinon, on retourne le backup
return c == 'o' || c == 'O' ? p : backup;
}
abstract class Image
{
public abstract Image Cloner();
public ConsoleColor Couleur { get; set; }
public void Dessiner() // Idiome NVI : non-virtual interface
{
ConsoleColor avant = Console.ForegroundColor;
Console.ForegroundColor = Couleur;
DessinerImpl();
Console.ForegroundColor = avant;
}
protected abstract void DessinerImpl();
protected Image(Image autre) : this(autre.Couleur)
{
}
public Image(ConsoleColor couleur)
{
Couleur = couleur;
}
}
class Bmp : Image
{
public override Bmp Cloner() => new(this);
protected Bmp(Bmp autre) : base(autre) { }
public Bmp(ConsoleColor couleur) : base(couleur) { }
protected override void DessinerImpl()
{
Console.WriteLine($"Bmp de couleur {Couleur}");
}
}
class Png : Image
{
public override Png Cloner() => new(this);
protected Png(Png autre) : base(autre) { }
public Png(ConsoleColor couleur) : base(couleur) { }
protected override void DessinerImpl()
{
Console.WriteLine($"Png de couleur {Couleur}");
}
}
class Jpeg : Image
{
public override Jpeg Cloner() => new(this);
protected Jpeg(Jpeg autre) : base(autre) { }
public Jpeg(ConsoleColor couleur) : base(couleur) { }
protected override void DessinerImpl()
{
Console.WriteLine($"Jpeg de couleur {Couleur}");
}
}
- Présentation de l'activité pour cette semaine. Attention :
les activités sont cumulatives, alors ne prenez pas de retard!
- Cette semaine, votre activité sera (à venir)
boites-v1.html
- Notez que le code proposé est en C# 9. Vous pouvez le
« simplifier » (légèrement) avec une version plus récente du
langage
À titre de rappel :
- Avec le schéma de conception
Fabrique,
une classe ou une fonction est responsable de créer des objets
- Pourquoi? Plusieurs raisons sont possibles :
- Parfois, c'est qu'on a besoin d'une construction en deux temps (p.ex.:
Thread th = new(...); puis th.Start(),
ou encore lire des données au clavier puis construire l'objet)
- Parfois, c'est pour une question de gestion d'erreurs (p.ex.: un constructeur n'a pas de type de retour, donc sa capacité à signaler un problème est limitée, typiquement aux levées d'exceptions)
- Parfois, on ne veut pas révéler le type d'objet construit, on veut juste exposer une interface,
ou encore on veut choisir le type effectivement construit en fonction des circonstances
- Parfois, les paramètres suppléés ne sont pas appropriés pour un constructeur
- etc.
Pour le schéma de conception
Visiteur, nous avons fait un bref exemple (un peu
simpliste), soit (https://dotnetfiddle.net/DAJeDg) :
using System;
using System.Collections;
using System.Collections.Generic;
var lst = new Liste<string>();
foreach (var s in new[] { "J'aime", "mon", "prof" })
lst.AjouterFin(s);
lst.Accepter(s => Console.Write($"{s} "));
Console.WriteLine();
string plusseLongue = null;
lst.Accepter(s =>
{
if (plusseLongue == null || s.Length > plusseLongue.Length)
plusseLongue = s;
});
Console.WriteLine($"Chaîne la plusse longue : {plusseLongue}");
string plusseCourte = null;
lst.Accepter(s =>
{
if (plusseCourte == null || s.Length < plusseCourte.Length)
plusseCourte = s;
});
Console.WriteLine($"Chaîne la plusse courte : {plusseCourte}");
class ListeVideException : Exception { }
// modélise une liste simplement chaînée dont chaque noeud "contient" un T
class Liste<T> : IEnumerable<T> where T : IEquatable<T>
{
public IEnumerator<T> GetEnumerator() =>
new Énumérateur(Tête);
IEnumerator IEnumerable.GetEnumerator() =>
new Énumérateur(Tête);
// un énumérateur de C# / un itérateur de Java, modélise
// une séquence à demi ouverte (debut, fin]
class Énumérateur : IEnumerator<T>
{
Noeud Cur { get; set; }
public Énumérateur(Noeud tête)
{
Cur = new (default);
Cur.Succ = tête;
}
public bool MoveNext()
{
if (Cur.Succ == null)
return false;
Cur = Cur.Succ;
return true;
}
public void Reset() => throw new NotImplementedException();
public void Dispose() { }
public T Current => Cur.Valeur;
object IEnumerator.Current => Cur.Valeur;
}
class Noeud
{
public T Valeur { get; init; }
public Noeud Succ { get; set; } = null;
public Noeud(T val)
{
Valeur = val;
}
}
Noeud Tête { get; set; } = null;
Noeud Queue { get; set; } = null;
public bool EstVide => Tête == null;
public void AjouterDébut(T val)
{
var noeud = new Noeud(val);
if (EstVide)
Tête = Queue = noeud;
else
{
noeud.Succ = Tête;
Tête = noeud;
}
++Count;
}
public void AjouterFin(T val)
{
Noeud noeud = new (val);
if (EstVide)
Tête = Queue = noeud;
else
{
Queue.Succ = noeud;
Queue = noeud;
}
++Count;
}
public void SupprimerDébut()
{
if (EstVide)
throw new ListeVideException();
Tête = Tête.Succ;
if (Tête == null)
Queue = null;
--Count;
}
public T PeekDébut() =>
EstVide? throw new ListeVideException(): Tête.Valeur;
public T PeekFin()
{
if (EstVide)
throw new ListeVideException();
return Queue.Valeur;
}
//public static Liste<T> Dupliquer(Liste<T> src)
//{
// Liste<T> dest = new();
// for (Noeud p = src.Tête; p != null; p = p.Succ)
// dest.AjouterFin(p.Valeur);
// return dest;
//}
public Liste<T> Dupliquer()
{
Liste<T> dest = new();
for (Noeud p = Tête; p != null; p = p.Succ)
dest.AjouterFin(p.Valeur);
return dest;
}
public int Count { get; private set; } = 0;
public void ForEach(Action<T> f)
{
foreach(T val in this)
f(val);
}
public bool Contains(T elem)
{
foreach(T val in this)
if(val.Equals(elem))
return true;
return false;
}
public Liste()
{
}
public Liste(IEnumerable<T> objs)
{
foreach (T e in objs)
AjouterFin(e);
}
public void Accepter(Action<T> f)
{
ForEach(f);
}
}
Portez évidemment attention à la méthode Accepter...
Notez le lien avec ForEach (dans le cas de Liste<T>, du moins; un
« foreach », au fond, c'est
une version limitée d'un visiteur).
|
