Date |
Séance |
Détails |
20 août
|
T00
|
Au menu :
Notez bien les identifiants pour les quatre documents
que vous pourrez vous procurer à la coop (si vous en exprimez le souhait;
voir plus haut pour des détails) :
- POO –
Volume 00, v. 1,97 (388 pages) →
1A18-196
- POO – Volume 01, v. 1,92 (265
pages) → 1A18-197
- POO – Volume 02, v. 1,995 (288
pages) → 1A18-198
- POO – Volume 03, v. 1,9985 (314
pages) → 1A18-199
|
24 août
|
L00
|
Au menu :
- Travail sur les exercices de base (exercices,
document de support),
à remettre au début de la séance L01(je ramasserai EX04
en format
imprimé). Je ramasserai
EX04.
- Je m'attends à ce que, suite à votre bon travail :
- le code n'ait plus de fuites de ressources (attention : ce n'est pas
parce qu'une fonction n'est pas appelée dans le
main() de test que je vous ai donné en accompagnement qu'elle
a le droit de fuir!)
- le code ne plante pas (ça semble évident, mais tout de même)
- les irritants suivants soient réglés (ne faites cette partie qu'une
fois les fuites et les plantages réglés, sinon vous allez vous empêtrer
inutilement dans la complexité) :
- remarquez que la méthode permettant de calculer le nombre d'éléments dans
une ListeEntiers doit présentement compter les
éléments. Ainsi, plus la liste contiendra d'éléments et plus l'exécution de
cette fonction sera longue (algorithme de
complexité O(n) où n est la
longueur de la liste). C'est très agaçant, et il serait préférable d'avoir un
algorithme en temps constant (complexité O(1))
- remarquez que la méthode permettant d'ajouter un élément à une
ListeEntiers doit parcourir cette liste pour en trouver le point d'insertion.
Ainsi, plus la liste contiendra d'éléments et plus l'exécution de cette
fonction sera longue (algorithme de
complexité O(n) où n est la longueur de
la liste). C'est très agaçant, et il serait préférable d'avoir un algorithme
en temps constant (complexité O(1))
- évidemment, si vous constatez d'autres irritants, corrigez-les!
- une fois ces changements apportés, assurez-vous que les autres méthodes
fonctionnent encore (un programme de test plus élaboré vous sera utile pour
cette fin). En particulier, la méthode qui inverse l'ordre des éléments d'une
liste bénéficierait d'un peu d'amour de votre part
Vous aurez droit à un petit bonus si vous ajustez la méthode permettant
d'inverser l'ordre des éléments de la liste pour qu'elle n'ait plus recours à
de l'allocation dynamique de mémoire.
|
27 août
|
T01
|
Au menu :
- Travail sur les exercices de base (exercices,
document de support,
solutionnaire),
à remettre au début de la séance L01. Voir L00 pour
plus de détails. Je ramasserai
EX04.
- À ce sujet :
- important : avez-vous bien implémenté la
Sainte-Trinité?
- utile : avez-vous implémenté le mouvement? C'est pas strictement
nécessaire ici, mais ce serait une excellente idée
Puisque nous ne nous verrons pas lundi prochain, je vous propose tout de
suite le travail qui sera à remettre à la séance
L02 :
- Exercice de rédaction d'une ListeEntiers,,
représentant une liste simplement chaînée d'entiers, en
Java ou en
C# (à votre choix)
- Peu importe que votre code de ListeEntiers
soit écrit en
Java ou en
C#, cette classe doit offrir au minimum les services suivants :
- constructeur par défaut, qui crée une liste vide
- mécanisme pour dupliquer une liste, donc créer une nouvelle liste
distincte de l'originale mais équivalente à cette dernière
- deux listes a et
b sont équivalentes si elles ont le même nombre de noeuds, et
si les noeuds de ces deux listes ont les mêmes valeurs dans le même
ordre
- mécanisme permettant d'inverser les éléments d'une liste
- mécanisme permettant d'ajouter un élément à une extrémité de la
liste
- mécanisme permettant d'extraire un élément à l'autre extrémité de la
liste
- mécanisme permettant de connaître le nombre d'éléments dans la
liste
- mécanisme permettant de tester la liste pour savoir si elle est
vide ou non
- mécanisme pour comparer deux listes et savoir si elles sont
équivalentes
- mécanisme pour afficher les éléments d'une liste sur un flux
- mécanisme pour vider une liste
- Consignes d'ordre général :
- visez à respecter les
idiomes de votre langage (si vous faites du
Java, faut que ça respecte les pratiques du code
Java; si vous faites du
C#, faut que ça respecte les pratiques du code
C#)
- utilisez les
exceptions
de manière judicieuse
- évitez les fuites de ressources
- Il faut que votre programme de test fasse au minimum les opérations
suivantes à l'aide d'instances de votre type
ListeEntiers :
- tester chacun des services ci-dessus
- valider que si une liste est une copie d'une autre liste, les deux
peuvent être modifiées indépendamment l'une de l'autre
|
31 août
|
L01
|
Au menu :
Maintenant que vous avez remis
EX04, je vous propose un solutionnaire
- Survol syntaxique de
C# pour celles et ceux qui ne le connaissent pas
- Survol syntaxique de
Java pour celles et ceux qui ne le connaissent pas
- Travailler sur votre classe ListeEntiers,
représentant une liste simplement chaînée d'entiers, en
Java ou en
C# (à votre choix)
|
3 septembre
|
s/o
|
Fête du travail
|
7 septembre
|
L02
|
Au menu :
- Remettre, en format imprimé, votre classe
ListeEntiers,
représentant une liste simplement chaînée d'entiers, en
Java ou en
C# (à votre choix)
- À titre exploratoire, transformez ListeEntiers
en Liste<T> et faites des tests avec
une Liste<int> et avec une
Liste<string> en
C#, ou Liste<Integer>
et Liste<String> en
Java
- Ajoutez les services suivants :
- une méthode de classe acceptant en paramètre deux
Liste<T> et retournant une liste contenant la concaténation du
contenu de ces deux listes. Ainsi, si on lui passe en paramètre une
liste contenant "J'aime ",
"mon " et "prof " de même qu'une
autre liste contenant "de " et
"prog", la liste retournée devra contenir
"J'aime ", "mon ",
"prof ", "de " et
"prog" dans l'ordre
- une méthode de classe acceptant en paramètre deux
Liste<T> et retournant true seulement
si ces deux listes sont « égales » (même nombre de noeuds,
noeuds de même valeur dans le même ordre)
Prudence : en
Java comme en
C#, les objets sont tous manipulés indirectement, à travers des
références (à toutes fins pratiques, à travers des pointeurs) ce qui
signifie que toute référence peut être nulle...
|
10 septembre
|
T02
|
Au menu :
Voici un petit défi de programmation
pour vous :
Seul ou par équipe de deux personnes, définissez une
classe Mutex capable de
représenter, pour une plateforme donnée, un mutex « système » ou un mutex
local au processus, selon un choix fait à la construction.
Plus précisément, avec Microsoft
Windows, votre classe encapsulera un
CRITICAL_SECTION ou un
HANDLE
sur un mutex, et offrira les services
« normaux » pour une telle
classe (construire, détruire, obtenir, relâcher).
Votre classe se voudra sécuritaire à utiliser. Conséquemment, vous chercherez
à réduire les risques d'erreurs dans le code client (mutex non libérés, fuites
de ressources, et autres irritants découlant d'un usage incorrect de votre
classe).
Souvenez-vous que la maxime de
Scott Meyers : « on ne peut empêcher un
individu qui insiste pour faire des bêtises de se placer dans une situation
déplaisante, mais on peut lui fournir des outils de qualité qui réduiront ce
risque » (traduction libre). C'est ce que nous visons ici : une classe avec laquelle il est plus
simple de bien travailler que de mal travailler.
Les méthodes qui peuvent être
const le seront. Vous
viserez plus particulièrement à ce que les méthodes obtenir()
et relacher() soient const.
Notez que, si vous souhaitez utiliser un std::lock_guard
avec votre propre classe Mutex, vous pouvez
appeler ces deux méthodes lock() et
unlock().
Le
code client ne doit pas être couplé de quelque manière que ce soit à la
plateforme (vous ne devez rien laisser filtrer pour lui du système
d'exploitation sous-jacent).
Quelques questions auxquelles je vous suggère de
réfléchir :
- Doit-on implémenter la Sainte-Trinité
pour cette classe? Expliquez votre réponse
- Doit-on implémenter le mouvement
pour cette classe? Expliquez votre réponse
- Quel est l'espace requis en mémoire pour votre
implémentation? Pourrait-elle être plus compacte? Cela serait-il
avantageux?
|
14 septembre
|
L03
|
Au menu :
- Suite du travail entamé à la séance
T02
|
17 septembre
|
T03
|
Au menu :
- Suite et fin du travail entamé à la séance
T02
Certains m'ont dit ne pas être certains de savoir comment tester le bon
fonctionnement de leur classe Mutex. Voici un possible programme de test, qui
suppose l'existence des constantes Mutex::Local et Mutex::Systeme
(il y a
plusieurs manières de procéder; ceci n'est que l'une d'entre elles).
Je
supposerai la présence de méthodes const nommées obtenir()
et relacher(), alors
adaptez le code de test en fonction des noms que vous aurez choisis :
#include "Mutex.h"
#include <thread>
#include <utility>
using namespace std;
auto test(const Mutex & m) {
enum { N = 1'000'000 };
int n = 0;
thread th0{ [&] {
for(int i = 0; i != N; ++i) {
m.obtenir();
++n;
m.relacher();
}
} };
thread th1{ [&] {
for(int i = 0; i != N; ++i) {
m.obtenir();
++n;
m.relacher();
}
} };
th0.join();
th1.join();
return pair{ n, 2 * N };
}
#include <iostream>
#include <locale>
int main() {
locale::global(locale{ "" });
Mutex m0{ Mutex::Local };
auto [n0,N0] = test(m0);
cout << "Local. Compté : " << n0 << ", attendu : "<< N0 << endl;
Mutex m1{ Mutex::Systeme };
auto [n1,N1] = test(m1);
cout << "Système. Compté : " << n1 << ", attendu : "<< N1 << endl;
}
|
21 septembre
|
L04
|
Au menu :
- Au début de la séance, vous devez me remettre, en format imprimé,
votre classe Mutex et un exemple de code client
utilisant cette classe
- Un solutionnaire possible est
celui-ci
Petit défi de programmation pour vous :
Par équipe de deux (ou trois, si tous s'impliquent)
personnes, définissez une classe tite_chaine
représentant une
petite chaîne de caractères (susceptible d'être utilisée dans un système
embarqué ou dans un jeu vidéo).
Vos contraintes sont les
suivantes :
- Essentiel :
sizeof(tite_chaine)==256
- Essentiel : aucune allocation dynamique de mémoire ne doit être
faite dans les méthodes d'une tite_chaine
- Essentiel : si s est une tite_chaine, alors s.size()
retourne sa
taille, exprimée en nombre de caractères, et est en temps constant
(complexité O(1)
)
-
Invariant : la taille d'une tite_chaine, en nombre de caractères,
doit être entre 0 et 255
inclusivement
- Essentiel : la
Sainte-Trinité
doit être supportée
par votre classe
- Essentiel : les opérateurs suivants doivent être offerts :
opérateurs relationnels (==, !=, <, <=, >
et >=), opérateur []
en
version const et non-const
- Essentiel : offrir une méthode empty()
retournant true seulement si
la tite_chaine est vide et qui s'exécute
en temps constant (complexité O(1)
)
-
Invariant : une tite_chaine
est vide si sa taille est zéro
- Essentiel : un constructeur par défaut de tite_chaine
doit construire une chaîne vide
- Essentiel : offrir un constructeur prenant en paramètre un
const char* (chaîne ASCIIZ)
- Essentiel : offrir un constructeur prenant en paramètre un
const std::string&
Quelques questions auxquelles je vous suggère de réfléchir :
- Doit-on implémenter la
Sainte-Trinité
pour cette classe? Expliquez votre réponse
- Doit-on implémenter le
mouvement
pour cette classe? Expliquez votre réponse
- Comment gérerez-vous les constructeurs recevant un
paramètre susceptible de violer vos
invariants (p. ex. : une chaîne de
plus de 255 caractères)?
- Discussion des choix de design
- Élaborer un code de test correct pour tite_chaine
Prenez soin de justifier par écrit vos choix
d'implémentation. Prenez aussi soin de documenter les
préconditions de vos fonctions, leurs
postconditions, leur complexité
algorithmique, de même que et
invariants de votre classe. Enfin, implémentez votre design
et testez-le
avec rigueur.
|
24 septembre
|
T04
|
Pour ma part, je serai à CppCon 2018.
Vous pourrez me suivre (à travers
../../../Sujets/Orthogonal/cppcon2018.html) si vous le souhaitez.
|
28 septembre
|
L05
|
Pour ma part, je serai à CppCon 2018.
Vous pourrez me suivre (à travers
../../../Sujets/Orthogonal/cppcon2018.html) si vous le souhaitez.
|
1er octobre
|
s/o
|
Élections provinciales (cours suspendus)
|
3 octobre
|
T05
|
Au menu :
- Retour sur le problème de la tite_chaine
- Effort de généricité et de rigueur. En vue de
T06,
vous devrez implémenter les algorithmes suivants, de telle sorte qu'ils soient
utilisables dans le respect des contraintes énoncées dans chaque cas. Chacun de
ces algorithmes existe dans la bibliothèque standard sous un autre nom, mais
vous n'avez pas le droit d'utiliser l'algorithme standard correspondant pour
résoudre le problème proposé (vous pouvez évidemment utiliser
std::swap()
ou d'autres algorithmes auxiliaires, mais je ne veux pas que votre
implémentation de est_trie() appelle
is_sorted(), à titre d'exemple). Ça peut sembler beaucoup, mais chacun est relativement
petit, et l'exercice est extrêmement pertinent à faire (de plus, je suspecte
que vous allez vous amuser!) :
- à titre de révision, implémentez inverser(debut,fin) où [debut,fin) représente une séquence à
demi-ouverte, de telle sorte que cet algorithme inverse l'ordre des éléments
de cette séquence (p. ex. : {2,3,5,7,11} deviendrait {11,7,5,3,2}). Il faut que cet algorithme soit applicable à un tableau, un
vector ou une list. Testez votre implémentation en vous assurant qu'elle
fonctionne avec une séquence contenant un nombre pair d'éléments, un nombre
impair d'éléments, et aucun élément (cas où debut==fin)
- implémentez rotater_gauche(debut,fin) où [debut,fin) représente une séquence à
demi-ouverte, de telle sorte que cet algorithme permute vers la gauche l'ordre des éléments
de cette séquence (p. ex. : {2,3,5,7,11} deviendrait {3,5,7,11,2}). Il faut que cet algorithme soit applicable à un tableau,
un
vector ou une list. Testez votre implémentation en vous assurant qu'elle
fonctionne avec une séquence contenant un nombre pair d'éléments, un nombre
impair d'éléments, et aucun élément (cas où debut==fin)
- implémentez rotater_droite(debut,fin) où [debut,fin) représente une séquence à
demi-ouverte, de telle sorte que cet algorithme permute vers la droite l'ordre des éléments
de cette séquence (p. ex. : {2,3,5,7,11} deviendrait {11,2,3,5,7}). Il faut que cet algorithme soit applicable à un tableau,
un
vector ou une list. Testez votre implémentation en vous assurant qu'elle
fonctionne avec une séquence contenant un nombre pair d'éléments, un nombre
impair d'éléments, et aucun élément (cas où debut==fin)
- à titre de révision, implémentez compter(debut,fin,val) où [debut,fin) représente une séquence à
demi-ouverte, de telle sorte que cet algorithme retourne le nombre d'éléments
e tels que e==val s'avère (p. ex. : pour vals={2,3,5,7,11}, compter(begin(vals),end(vals),3)==1).
Il faut que cet algorithme soit applicable à un tableau, un
vector une list ou une
forward_list. Testez votre implémentation en vous assurant qu'elle
fonctionne avec une séquence contenant un nombre pair d'éléments, un nombre
impair d'éléments, et aucun élément (cas où debut==fin)
- à titre de révision, implémentez compter_si(debut,fin,pred) où [debut,fin) représente une séquence à
demi-ouverte, de telle sorte que cet algorithme retourne le nombre d'éléments
e tels que pred(e) s'avère (p. ex. : pour vals={2,3,5,7,11}, compter_si(begin(vals),end(vals),[](int n){return n%2!=0;})==4).
Il faut que cet algorithme soit applicable à un tableau, un
vector une list ou une
forward_list. Testez votre implémentation en vous assurant qu'elle
fonctionne avec une séquence contenant un nombre pair d'éléments, un nombre
impair d'éléments, et aucun élément (cas où debut==fin)
- implémentez trouver(debut,fin,val) où [debut,fin) représente une séquence à
demi-ouverte, de telle sorte que cet algorithme retourne un itérateur sur
l'élément
e tel que e==val s'avère. Il faut que cet
algorithme soit applicable à un tableau, un
vector une list ou une
forward_list. Testez votre implémentation en vous assurant qu'elle
fonctionne avec une séquence contenant un nombre pair d'éléments, un nombre
impair d'éléments, et aucun élément (cas où debut==fin)
- implémentez trouver_si(debut,fin,pred) où [debut,fin)
représente une séquence à demi-ouverte, de telle sorte que cet algorithme
retourne un itérateur sur l'élément
e tel que pred(e) s'avère. Il faut que cet
algorithme soit applicable à un tableau, un
vector une list ou une
forward_list. Testez votre implémentation en vous assurant qu'elle
fonctionne avec une séquence contenant un nombre pair d'éléments, un nombre
impair d'éléments, et aucun élément (cas où debut==fin)
- implémentez est_trie(debut,fin) où [debut,fin)
représente une séquence à demi-ouverte, de telle sorte que cet algorithme
retourne true seulement si la séquence est triée.
Il faut que cet algorithme soit applicable à un tableau, un
vector une list ou une
forward_list. Testez votre implémentation en vous assurant qu'elle
fonctionne avec une séquence contenant un nombre pair d'éléments, un nombre
impair d'éléments, et aucun élément (cas où debut==fin)
- implémentez est_trie(debut,fin,pred) où [debut,fin)
représente une séquence à demi-ouverte, de telle sorte que cet algorithme
retourne true seulement si la séquence est triée
en fonction du prédicat pred. Il faut que cet
algorithme soit applicable à un tableau, un
vector une list ou une
forward_list. Testez votre implémentation en vous assurant qu'elle
fonctionne avec une séquence contenant un nombre pair d'éléments, un nombre
impair d'éléments, et aucun élément (cas où debut==fin)
- implémentez supprimer_duplicats(debut,fin) où [debut,fin)
représente une séquence à demi-ouverte triée, de telle sorte que cet
algorithme supprime les duplicats de cette séquence.
Il faut que cet algorithme soit applicable à un tableau, un
vector ou une list. Testez votre implémentation en vous assurant qu'elle
fonctionne avec une séquence contenant un nombre pair d'éléments, un nombre
impair d'éléments, et aucun élément (cas où debut==fin).
Cette fonction ne peut évidemment pas vraiment éliminer les éléments
de la séquence (elle ne connaît pas le conteneur et doit fonctionner même avec
un tableau!) alors pour « éliminer » un élément, elle doit le placer à la fin
de la séquence. Sa valeur de retour est la « nouvelle fin » de la séquence (un
itérateur sur le premier des éléments « éliminés »)
- Il serait facile de tricher en réalisant cet exercice, mais je vous invite
fortement à ne pas le faire, et à tirer profit de ce qu'ils peuvent vous
enseigner
Prudence : mercredi avec horaire du lundi
|
5 octobre
|
L06
|
Au menu :
- Travail sur les exercices présentés à
T05
|
8 octobre
|
s/o
|
Action de
grâce
|
9 octobre
|
T06
|
Au menu :
- À la fin du cours, remise de :
- la fonction est_trie(debut,fin,pred)
- la fonction rotater_droite(debut,fin)
Pour ne pas que vous sombriez dans l'ennui, voici une activité à
faire pour T07... Ceci peut
sembler beaucoup, mais c'est pas si mal... si vous n'attendez pas jusqu'à la dernière minute avant de
débuter!
Votre expérience avec la programmation générique en
C++ a soulevé en vous, j'en suis sûr, des questions face à la
programmation générique dans d'autres langages. C'est sûrement plus simple, vous
disiez-vous, avec un langage comme
C#, n'est-ce pas?
Alors voici : nous allons écrire en
C# les « mêmes » algorithmes
que ceux mis au point en
C++ depuis
T05.
Programmation générique avec
C#
Le piège : la programmation générique en
C#
est superficiellement semblable à la programmation générique en
C++. Par exemple, une fonction pour permuter deux valeurs peut s'exprimer
comme suit (si on escamote le
mouvement, que
C#
ne supporte pas) :
C++ (sans mouvement) |
C# |
template <class T>
void swap(T &a, T &b) {
T temp = a;
a = b;
b = temp;
}
struct Point {
int x {},
y {};
Point() = default;
constexpr Point(int x, int y) : x{ x }, y{ y } {
}
};
#include <string>
int main() {
using std::string;
int i0 = 3,
i1 = 5;
swap(i0, i1);
string s0 = "Tigidou",
s1 = "Yo";
swap(s0, s1);
Point p0{ 2, 3 },
p1{ -1, 0 };
swap(p0, p1);
}
|
using System;
namespace Bla
{
class Point
{
public int X { get; set; } = 0;
public int Y { get; set; } = 0;
Point(int x, int y)
{
X = x;
Y = y;
}
Point()
{
}
}
class Program
{
static void Swap<T>(ref T a, ref T b)
{
T temp = a;
a = b;
b = temp;
}
static void Main(string [] args)
{
int i0 = 3,
i1 = 5;
Swap(ref i0, ref i1);
string s0 = "Tigidou",
s1 = "Yo";
Swap(ref s0, ref s1);
Point p0 = new Point(2, 3),
p1 = new Point(-1, 0);
Swap(ref p0, ref p1);
}
}
}
|
Jusqu'ici, en se basant sur la fonction
template<class T> void swap(T&,T&) /
static void Swap<T>(ref T,ref T), les différences entre les deux langages
semblent bien mineures.
Une subtilité qui ne vous affectera pas pour ce travail est que la
programmation générique en
C#
ne fonctionne que pour les classes. Pour vous aider à utiliser des types
« primitifs »,
C#
fait du Boxing (créer un objet pour remplacer le primitif) et du Unboxing
(refaire un primitif à partir d'un objet) automatiquement. Ceci semble
transparent, mais ce n'est pas gratuit (un new est
fait en cachette à chaque fois) alors si vous utilisez
C#
professionnellement, portez attention aux coûts cachés de cette pratique.
Vous trouverez des exemples dans
../../../Sujets/Divers--cdiese/Genericite-lambdas.html
Expressions λ
En
C#,
les expressions λ sont moins puissantes que celles de
C++, mais elles sont aussi plus simples. Par exemple, une λ qui
accepte un nombre et retourne son carré serait :
C# |
C++ |
(x) => x * x
|
[](auto x){ return x * x; }
|
Pour
C#, l'équivalent des std::function
est un Func. Ainsi, ceci affichera 9 et Pair :
C# |
C++ |
Func<int,int> carré = (x) => x * x;
Func<int,int,bool> sommePaire = (x,y) =>
{
return (x + y) % 2 == 0;
};
Console.WriteLine(carré(3));
if (sommePaire(3,5))
{
Console.WriteLine("Pair");
}
|
function<int(int)> carre = [](auto x){ return x * x; };
function<bool(int,int)> somme_paire = [](int x, int y) {
return (x + y) % 2 == 0;
};
cout << carre(3);
if (somme_paire(3, 5)) {
cout << "Pair";
}
|
... affichera 9 et Pair.
Parcourir une collection générique avec
C#
Le langage
C#,
comme bien d'autres langages, permet d'exprimer des algorithmes génériques sur
des collections (terme
.NET pour ce que
C++ appelle des
conteneurs).
Vous trouverez de l'information et des exemples à ce sujet sur
../../../Sujets/Divers--cdiese/Enumerateur-sliste.html
où est présenté un énumérateur (terme
.NET pour ce que
C++ appelle des
itérateurs).
Votre mandat
Votre mandat sera donc d'écrire les algorithmes couverts depuis
T05, mais en
C#.
Pour des raisons qui seront expliquées plus bas, vous ne pourrez pas avoir
exactement les mêmes signatures dans les deux langages, alors les consignes
détaillées seront légèrement différentes.
Le programme principal sera imposé :
namespace AlgosGénériques
{
class Program
{
static void Main(string[] args)
{
Tests.TesterInverser();
Tests.TesterRotaterGauche();
Tests.TesterRotaterDroite();
Tests.TesterCompter();
Tests.TesterCompterSi();
Tests.TesterTrouver();
Tests.TesterTrouverSi();
Tests.TesterEstTrié();
Tests.TesterSupprimerDuplicats();
}
}
}
Le code de test sera lui aussi imposé :
J'ai mis tous les tests dans une même classe, pour faciliter les choses.
Comme vous pouvez le voir avec le programme principal ci-dessus, la syntaxe pour
accéder à un membre d'un namespace, à un membre
d'une classe ou à un membre d'un objet est la même (on utilise le
'.'). |
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static AlgosGénériques.Algos;
namespace AlgosGénériques
{
class Tests
{
|
La méthode Afficher() affichera chaque élément d'une séquence.
Remarquez le recours à une chaîne préfixée par un $.
Ceci provoque ce qu'on appelle du String Interpolation, ce qui
remplacera le code entre accolades par la valeur de l'expression qu'il
représente (ici, la valeur de la variable obj). |
static void Afficher<T>(IEnumerable<T> e)
{
Console.Write("{ ");
foreach (T obj in e)
{
Console.Write($"{obj} ");
}
Console.Write("} ");
}
|
Pour alléger le tout, chaque algorithme sera testé par une paire de
méthodes : une première qui réalisera un test sur un paramètre ou un groupe de
paramètres, et... |
private static void TesterInverser<C,T>(C coll, Func<IEnumerable<T>,C> f)
where C : IEnumerable<T>
{
Console.Write("Avant inversion : ");
Afficher(coll);
coll = Inverser(coll, f);
Console.Write("Après inversion : ");
Afficher(coll);
Console.WriteLine();
Console.WriteLine(new string('-', 70));
}
|
... une autre qui appellera la première avec divers groupes de
paramètres.
TesterInverser() est un exemple :
- Tout d'abord, notez qu'Inverser() est
générique, et opère sur un IEnumerable<T>
- La première prend une collectione de type C,
applique Inverser() dessus, et reconstruit un
C qu'elle retournera grâce à une fonction f
capable de transformer un IEnumerable<T> en
C
- Les tests réalisés se font sur des tableaux et des
List de int et de float,
incluant une collection vide
Remarquez le where dans la première des deux fonctions : ceci exprime une
contrainte sur le type C
|
public static void TesterInverser()
{
TesterInverser(
new int[] { 2, 3, 5, 7, 11 },
new Func<IEnumerable<int>, int[]>((e) => e.ToArray())
);
TesterInverser(
new float [] { 2.5f, 3.5f, 5.5f, 7.5f },
new Func<IEnumerable<float>, float[]>((e) => e.ToArray())
);
TesterInverser(
new List<int> { 2, 3, 5, 7, 11 },
new Func<IEnumerable<int>, List<int>>((e) => e.ToList())
);
TesterInverser(
new List<int>(),
new Func<IEnumerable<int>, List<int>>((e) => e.ToList())
);
}
|
Les tests pour les algorithmes RotaterGauche()
et RotaterDroite() sont sur le même modèle
que ceux sur Inverser(). |
private static void TesterRotaterGauche<C, T>(C coll, Func<IEnumerable<T>, C> f)
where C : IEnumerable<T>
{
Console.Write("Avant permutation à gauche : ");
Afficher(coll);
coll = RotaterGauche(coll, f);
Console.Write("Après permutation à gauche : ");
Afficher(coll);
Console.WriteLine();
Console.WriteLine(new string('-', 70));
}
public static void TesterRotaterGauche()
{
TesterRotaterGauche(
new int[] { 2, 3, 5, 7, 11 },
new Func<IEnumerable<int>, int[]>((e) => e.ToArray())
);
TesterRotaterGauche(
new float[] { 2.5f, 3.5f, 5.5f, 7.5f },
new Func<IEnumerable<float>, float[]>((e) => e.ToArray())
);
TesterRotaterGauche(
new List<int> { 2, 3, 5, 7, 11 },
new Func<IEnumerable<int>, List<int>>((e) => e.ToList())
);
TesterRotaterGauche(
new List<int>(),
new Func<IEnumerable<int>, List<int>>((e) => e.ToList())
);
}
private static void TesterRotaterDroite<C, T>(C coll, Func<IEnumerable<T>, C> f)
where C : IEnumerable<T>
{
Console.Write("Avant permutation à droite : ");
Afficher(coll);
coll = RotaterDroite(coll, f);
Console.Write("Après permutation à droite : ");
Afficher(coll);
Console.WriteLine();
Console.WriteLine(new string('-', 70));
}
public static void TesterRotaterDroite()
{
TesterRotaterDroite(
new int[] { 2, 3, 5, 7, 11 },
new Func<IEnumerable<int>, int[]>((e) => e.ToArray())
);
TesterRotaterDroite(
new float[] { 2.5f, 3.5f, 5.5f, 7.5f },
new Func<IEnumerable<float>, float[]>((e) => e.ToArray())
);
TesterRotaterDroite(
new List<int> { 2, 3, 5, 7, 11 },
new Func<IEnumerable<int>, List<int>>((e) => e.ToList())
);
TesterRotaterDroite(
new List<int>(),
new Func<IEnumerable<int>, List<int>>((e) => e.ToList())
);
}
|
Les tests pour compter les occurrences d'un élément dans une collection
sont sans doute les plus simples du lot.
Quand vous écrirez votre propre algorithme Compter(),
notez que vous voudrez probablement exiger (par une clause where) que le type
T des éléments de votre collection soient
IComparable, car comparer deux objets en
C#
est une tâche plus complexe qu'en
C++, où utiliser == suffit souvent |
private static void TesterCompter<T>(IEnumerable<T> coll, T obj)
{
Console.Write("La collection ");
Afficher(coll);
Console.WriteLine($"contient {Compter(coll, obj)} occurrence(s) de {obj}");
Console.WriteLine(new string('-', 70));
}
public static void TesterCompter()
{
TesterCompter(new int[] { 2, 3, 5, 7, 11, 3 }, 3);
TesterCompter(new List<int> { 2, 3, 5, 7, 11, 3 }, 7);
TesterCompter(new List<string> { "J'aime", "mon", "prof" }, "prof");
TesterCompter(new List<string>(), "prof");
}
private static void TesterCompterSi<T>(IEnumerable<T> coll, Func<T,bool> pred, string crit)
{
Console.Write("La collection ");
Afficher(coll);
Console.WriteLine($"contient {CompterSi(coll, pred)} occurrence(s) respectant le critère {crit}");
Console.WriteLine(new string('-', 70));
}
public static void TesterCompterSi()
{
TesterCompterSi(new int[] { 2, 3, 5, 7, 11 }, (n) => n % 2 == 0, "pair");
TesterCompterSi(new int[] { 2, 3, 5, 7, 11 }, (n) => n % 2 != 0, "impair");
TesterCompterSi(new int[] { 2, 3, 5, 7, 11 }, (n) => n < 0, "négatif");
}
|
Vos algorithmes Trouver() et
TrouverSi() devront retourner des IEnumerator<T>.
Le modèle de
C#
ne permet pas de modéliser un objet non-trouvé par un itérateur sur la fin d'une
séquence; en retour, les énumérateurs de
C#
sont des objets, et tous les objets de ce langage sont créés dynamiquement et
manipulés par des références (sortes de pointeurs), donc il est possible de
retourner null pour représenter un échec de la
recherche. |
private static void TesterTrouver<T>(IEnumerable<T> coll, T obj)
{
Console.Write("La collection ");
Afficher(coll);
var it = Trouver(coll, obj);
if (it != null)
{
Console.WriteLine($"contient {obj}");
}
else
{
Console.WriteLine($"ne contient pas {obj}");
}
Console.WriteLine(new string('-', 70));
}
public static void TesterTrouver()
{
TesterTrouver(new int[] { 2, 3, 5, 7, 11 }, 2);
TesterTrouver(new List<int> { 2, 3, 5, 7, 11 }, 7);
TesterTrouver(new List<int> { 2, 3, 5, 7, 11 }, 8);
TesterTrouver(new int[0], 8);
}
private static void TesterTrouverSi<T>(IEnumerable<T> coll, Func<T,bool> pred, string crit)
{
Console.Write("La collection ");
Afficher(coll);
var it = TrouverSi(coll, pred);
if (it != null)
{
Console.WriteLine($"contient au moins un objet respectant le critère {crit}");
}
else
{
Console.WriteLine($"ne contient pas d'objet respectant le critère {crit}");
}
Console.WriteLine(new string('-', 70));
}
public static void TesterTrouverSi()
{
TesterTrouverSi(new int[] { 2, 3, 5, 7, 11 }, (n) => n == 2, "vaut 2");
TesterTrouverSi(new List<int> { 2, 3, 5, 7, 11 }, (n) => n % 2 == 0, "pair");
TesterTrouverSi(new List<int> { 2, 3, 5, 7, 11 }, (n) => n < 0, "négatif");
TesterTrouverSi(new int[0], (n) => n == 8, "vaut 8");
}
|
Les tests pour EstTrié(), avec ou sans un
prédicat d'ordonnancement, ne sont pas vraiment plus complexes que les tests
précédents.
En fait, EstTrié() est probablement l'algorithme
qui ressemblera le plus à celui que vous aurez exprimé en
C++ |
private static void TesterEstTrié<T>(IEnumerable<T> coll) where T : IComparable
{
Console.Write("La collection ");
Afficher(coll);
if (EstTrié(coll))
{
Console.WriteLine("est triée");
}
else
{
Console.WriteLine("n'est pas triée");
}
Console.WriteLine(new string('-', 70));
}
private static void TesterEstTrié<T>(IEnumerable<T> coll, Func<T,T,bool> pred, string crit)
where T : IComparable
{
Console.Write("La collection ");
Afficher(coll);
if (EstTrié(coll, pred))
{
Console.WriteLine($"est triée en ordre {crit}");
}
else
{
Console.WriteLine($"n'est pas triée en ordre {crit}");
}
Console.WriteLine(new string('-', 70));
}
public static void TesterEstTrié()
{
TesterEstTrié(new int[] { 2, 3, 5, 7, 11 });
TesterEstTrié(new int[] { 2, 5, 3, 7, 11 });
TesterEstTrié(new int[] { 11, 7, 5, 3, 2 }, (x,y) => y < x, "décroissant");
TesterEstTrié(new int[] { 2, 3, 5, 7, 11 }, (x, y) => y < x, "décroissant");
TesterEstTrié(new List<string> { "J'aime", "mon", "prof" });
}
|
Enfin, SupprimerDuplicats() aura un
comportement semblable à celui de son cousin en
C++.
Notez que le test de base a deux clauses where,
l'une s'appliquant à la collection à parcourir et l'autre s'appliquant aux
éléments de cette collection. Ça vous donnera une idée de la syntaxe à utiliser
dans de telles circonstances
|
private static void TesterSupprimerDuplicats<C, T>(C coll, Func<IEnumerable<T>, C> f)
where C : IEnumerable<T>
where T : IComparable
{
Console.Write("Avant suppression des doublons : ");
Afficher(coll);
coll = SupprimerDuplicats(coll, f);
Console.WriteLine();
Console.Write("Après suppression des doublons: ");
Afficher(coll);
Console.WriteLine();
Console.WriteLine(new string('-', 70));
}
public static void TesterSupprimerDuplicats()
{
TesterSupprimerDuplicats(
new int[] { 2, 3, 5, 7, 11 },
new Func<IEnumerable<int>, int[]>((e) => e.ToArray())
);
TesterSupprimerDuplicats(
new int[] { 2, 3, 3, 5, 7, 11 },
new Func<IEnumerable<int>, int[]>((e) => e.ToArray())
);
TesterSupprimerDuplicats(
new List<int>{ 2, 3, 5, 7, 11, 11, 11 },
new Func<IEnumerable<int>, List<int>>((e) => e.ToList())
);
}
}
}
|
Voilà, vous avez le code de test et plusieurs pistes. Il ne vous reste plus
qu'à coder les méthodes!
Prudence : mardi avec horaire du lundi
|
12 octobre
|
L07
|
Au menu :
- Travail sur les exercices présentés lors de
T06
|
15 octobre
|
T07
|
Au menu :
- Travail sur les exercices présentés lors de
T06
|
19 octobre
|
L08
|
Au menu :
- Poursuite et fin du travail sur les exercices présentés lors de
T06
- Remise des fonctions suivantes :
- la méthode EstTrié()
- la méthode RotaterDroite()
- mini bonus si vous remettez aussi un bon SupprimerDuplicats()
- Exceptionnellement, je serai disponible en format « tutorat à
distance » pour cette séance
|
22 octobre
|
T08
|
Au menu :
- Pour le reste de la séance, et pour la prochaine, un petit exercice (à
remettre au début de T09). Soit le code suivant :
#include <ostream>
#include <istream>
#include <string>
#include <string_view>
#include <algorithm>
#include <memory>
#include <vector>
using namespace std;
template <class T, class U>
constexpr bool est_entre_demi_ouvert(const T &val, const U &seuilmin, const U &seuilmax) {
return seuilmin <= val && val < seuilmax;
}
template <class T, class U>
constexpr bool est_entre_inclusif(const T &val, const U &seuilmin, const U &seuilmax) {
return seuilmin <= val && val <= seuilmax;
}
class ContrainteNonRespectee { };
template <class T, class Pred>
const T& valider_contrainte(Pred pred, const T &val) {
return !pred(val)? throw ContrainteNonRespectee{} : val;
}
class Monstre {
string nom_;
public:
Monstre(string_view nom) : nom_{ nom } {
}
string nom() const {
return nom_;
}
virtual ostream& hurler(ostream&) const = 0;
virtual void mettre_a_jour(ostream&, istream&) = 0;
virtual ~Monstre() = default;
};
ostream& operator<<(ostream &os, const Monstre &monstre) {
return monstre.hurler(os);
}
bool operator==(const Monstre &a, const Monstre &b) {
return a.nom() == b.nom();
}
bool operator!=(const Monstre &a, const Monstre &b) {
return !(a == b);
}
class Bestiole : public Monstre {
double agacement_;
public:
Bestiole(string_view nom, double agacement)
: Monstre{ nom },
agacement_{ valider_contrainte([](double val) {
return est_entre_demi_ouvert(val, 0.0, 1.0);
}, agacement) }
{
}
friend void RendreMoinsAchalant(Bestiole&);
friend void RendrePlusAchalant(Bestiole&);
double agacement() const {
return agacement_;
}
ostream& hurler(ostream &os) const override {
return os << "Je suis " << nom() << " la bestiole, achalant a " << agacement() * 100 << "%";
}
void mettre_a_jour(ostream &out, istream &in) override {
out << R"(Vos options :
1) rendre plus achalant
2) rendre moins achalant
Votre choix: )";
int choix;
while(in >> choix && !est_entre_inclusif(choix, 1, 2))
out << R"(Vos options :
1) rendre plus achalant
2) rendre moins achalant
Votre choix: )";
switch (choix) {
case 1:
RendrePlusAchalant(*this);
break;
case 2:
RendreMoinsAchalant(*this);
break;
}
}
};
class Bibitte : public Monstre {
int puanteur_;
double mechancete_;
public:
Bibitte(string_view nom, int puanteur, double mechancete)
: Monstre{ nom },
puanteur_{ valider_contrainte([](int val) {
return est_entre_inclusif(val, 1, 100);
}, puanteur) },
mechancete_{ valider_contrainte([](double val) {
return est_entre_demi_ouvert(val, 0.0, 1.0);
}, mechancete) }
{
}
friend void Laver(Bibitte&);
friend void Salir(Bibitte&);
int puanteur() const {
return puanteur_;
}
double mechancete() const {
return mechancete_;
}
ostream& hurler(ostream &os) const override {
return os << "Je suis " << nom() << " la bibitte; puant a " << puanteur() << "% et mechant a " << mechancete() * 100 << "%";
}
void mettre_a_jour(ostream &out, istream &in) override {
out << R"(Vos options :
1) laver
2) salir
Votre choix: )";
int choix;
while(in >> choix && !est_entre_inclusif(choix, 1, 2))
out << R"(Vos options :
1) laver
2) salir
Votre choix: )";
switch (choix) {
case 1:
Laver(*this);
break;
case 2:
Salir(*this);
break;
}
}
};
void Laver(Bibitte &b) {
b.puanteur_ = 1;
}
void Salir(Bibitte &b) {
b.puanteur_ = min(100, b.puanteur_ + 5);
}
void RendreMoinsAchalant(Bestiole &b) {
b.agacement_ -= b.agacement_ * 0.5;
}
void RendrePlusAchalant(Bestiole &b) {
b.agacement_ += (1.0 - b.agacement_) * 0.5;
}
template <class T>
unique_ptr<T> modifier_potentiellement(unique_ptr<T> p, ostream &out, istream &in) {
}
#include <iostream>
int main() {
vector<unique_ptr<Monstre>> v;
v.emplace_back(unique_ptr<Monstre> { new Bibitte{ "Joe", 30, 0.75 }});
v.emplace_back(unique_ptr<Monstre> { new Bestiole{ "Fred", 0.23 }});
v.emplace_back(unique_ptr<Monstre> { new Bestiole{ "Bill", 0.8 }});
v.emplace_back(unique_ptr<Monstre> { new Bibitte{ "Zebda", 66, 0.11 }});
v.emplace_back(unique_ptr<Monstre> { new Bestiole{ "Guy", 0.99 }});
for (auto & p : v) {
cout << "Avant: " << *p << '\n';
p = modifier_potentiellement(std::move(p), cout, cin);
cout << "Apres: " << *p << '\n';
}
}
Vous aurez remarqué que quelques sections de code manquent, sans doute
effacées par une créature immonde ou féroce. Votre mandat est de compléter
ce programme pour qu'il redevienne fonctionnel.
Que doit faire ce programme, me direz-vous? Simple :
- La fonction modifier_potentiellement()
doit offrir à l'usager de mettre à jour le Monstre
reçu en paramètre. La méthode polymorphique
mettre_a_jour() d'un Monstre vous
aidera en ce sens
- Une fois la mise à jour réalisée,
modifier_potentiellement() devra demander à l'usager s'il est
satisfait des changements. Si l'usager répond par l'affirmative, alors la
mise à jour sera conservée, sinon elle ne le sera pas
- Une manière simple d'implémenter ceci est de faire un duplicat de
l'objet au début de modifier_potentiellement(),
de modifier l'une des deux versions de l'objet en gardant l'autre
intacte, et de retourner l'objet modifié ou celui qui ne l'est pas, selon
le cas. Cependant, vous avez le droit d'être créatifs dans votre
démarche, dans la mesure où c'est propre, où ça fonctionne et où ça ne
provoque pas de fuites de ressources.
N'hésitez pas à poser des questions. Cet exercice est à faire sur une
base individuelle.
|
26 octobre
|
L09
|
Au menu :
- Classes polymorphiques et classes concrètes (Java,
C++,
C#)
- Retour sur le clonage (avec
C++, avec C#)
- Quand copier, quand cloner
- Comment copier, comment cloner
- Variadiques en
Java
- « Variadiques » en
C#
-
Variadiques en
C++
-
Fold Expressions en
C++
- Mention brève de
std::variant,
qui permet de faire (de manière plus moderne) bien des choses que le
polymorphisme classique fait, mais de manière souvent plus efficace
- Travail sur l'exercice distribué à la séance
T08
|
29 octobre
|
s/o
|
Journée pédagogique (cours suspendus)
|
2 novembre
|
s/o
|
Journée de mise à niveau (cours suspendus)
|
5 novembre
|
T09
|
Au menu :
- En début de séance, remettre l'exercice distribué à la séance
T08
- Classes terminales (avec C++, avec Java,
avec C#) : pourquoi
et comment
- Techniques
d'effacement de type
- Techniques de mise à jour dynamique d'éléments d'un logiciel (aperçu)
- Survol de quelques types standards en lien avec la matière du cours :
|
9 novembre
|
L10
|
Au menu :
|
12 novembre
|
T10
|
Au menu :
|
16 novembre
|
L11
|
Au menu :
|
19 novembre
|
T11
|
Au menu :
Nous illustrerons notre démarche à l'aide d'un problème concret : comment
extraire les identifiants d'un fichier source, puis compter le nombre
d'occurrences des mots clés d'un certain langage.
|
23 novembre
|
L12
|
Au menu :
|
26 novembre
|
T12
|
Au menu :
|
30 novembre
|
L13
|
Au menu :
|
3 décembre
|
T13
|
Au menu :
|
7 décembre
|
L14
|
Au menu :
|
10 décembre
|
T14
|
Au menu :
- Chic examen final plein d'amour! Droit aux documents papier seulement.
Exceptionnellement, la séance se tiendra au
P-148 de
10 h 45 à
13 h
- Remise de votre solution au problème des boîtes imbriquées
- Remise de la PFI
|