====== Partie III – Algorithmes génériques======

Dans la conclusion du cours, nous affirmons qu’un intérêt du polymorphisme, c’est de pouvoir écrire un algorithme « générique », c’est à dire un algorithme qui pourra fonctionner pour des objets représentant des données de plusieurs types.

Nous considérons un algorithme de tri très simple qui fonctionne sur des entiers :

<code cpp>
void insertion_sort(std::vector<int>& anArray)
{
	for (int i = 0; i < anArray.size(); i++)
	{
		for (int j = i + 1; j < anArray.size(); j++)
		{
			if (anArray[i] > anArray[j])
				std::swap(anArray[i], anArray[j]);
		}
	}
}
</code>

Cet algorithme fonctionne uniquement pour des entiers. Nous nous proposons de transformer cette fonction afin qu’elle puisse aussi bien trier des entiers mais aussi des réels ou des complexes.

===== Question n° 1=====

Pour ce faire, nous concevons une classe « abstraite » ayant comme nom « Base » qui expose les fonctions nécessaires à l’écriture de l’algorithme de tri. 

Nous souhaitons utiliser l’algorithme avec la signature suivante :

<code cpp>
void insertion_sort(std::vector<Base*>& anArray)
</code>

Quelles sont les méthodes virtuelles que la classe abstraite doit exposer ? 

<hidden Correction>

La classe doit exposée une méthode permettant de déterminer si un élément est plus grand que l'autre. Il peut s'agit soit d'une méthode testant si un élément est plus grand que l'autre :

<code cpp>
class Base
{
public: 
    virtual bool isGreater(const Base&) const = 0; 
        // Retourne true si l'objet courant est plus grand.
    ...
};
</code>

Nous pouvons ajouter éventuellement des méthodes complémentaires comme :

<code cpp>
    virtual bool isGreaterOrEqual(const Base&) const = 0; 
    virtual bool isLess(const Base&) const = 0; 
    virtual bool isLessOrEqual(const Base&) const = 0; 
    virtual bool isEqual(const Base&) const = 0; 
    virtual bool isNotEqual(const Base&) const = 0; 
</code>

Voire éventuellement une fonction ''compareTo'':

<code cpp>
    virtual int compareTo(const Base&) const = 0;
       // retourne -1 si l'instance courante est plus petite que l'instance passée en paramètre
       // retourne 0 si elles sont égales
       // retourne 1 si l'instance courante est plus grande que l'instance passée en paramètre.
</code>

</hidden>


===== Question n° 2=====

==== Question n° 2.1====

Ajouter à la classe de base ''Base'' une méthode purement virtuelle ''print()'' qui affiche le contenu de la classe sur la console.


<hidden Correction>

Il suffit d'ajouter la méthode suivante:

<code cpp>
class Base
{
    ...
public:
    ...
    virtual void print() const = 0;
    
}
</code>
</hidden>

==== Question n° 2.2 ====

Créer une fonction ''print(std::vector<Base*> anArray)'' qui prend un tableau en paramètre et affiche l’ensemble des éléments contenus dans le tableau sur la console.


<hidden Correction>

Il suffit d'énumérer les éléments dans le tableau ou dans le containeur.

Nous pouvons faire une version orientée tableau qui ressemblera à cette version.

void print(std::vector<Base*> anArray)
{
    std::cout << "[";
    int lastIndex = anArray.size()-1;
    if(lastIndex >= 0)
    {
        for(int i = 0; i < lastIndex; i++)
        {
            anArray[i]->print(); 
            std::cout << ", ";
        }
        anArray[lastIndex]->print(); 
    }
    std::cout << "]";
}

Si nous souhaitons être un peu plus "C++" dans l'esprit, nous accéderons par des itérateurs.

<code cpp>

template<typename iterator>
void print(iterator theStart, iterator theEnd)
{
    std::cout << "[";
    if (theStart != theEnd)
    {
        *theStart->print();
        theStart++;
        while (theStart != theEnd)
        {
            std::cout << ", ";
            *theStart->print();
        }
        std::cout << "]";
    }
}
</code>

</hidden>

===== Question n° 3 =====

===== Question n° 3.1 ====

Créer une classe Entier qui dérive de la classe « abstraite » ''Base'' et qui contient un champ ''m_value'' ayant comme type le type ''int''.


<hidden Correction>

En plus de contenir le champ entier ''m_value'', la classe doit définir le constructeur par défaut, le constructeur de conversion d'une valeur de type ''int'' vers l'objet ''Entier'' ainsi que la conversion d'un objet ''Entier'' vers une valeur de type ''int''.

<code cpp>
class Entier : public Base
{
private:
    int m_value;
public:
    Entier() : m_value(0) {}
    Entier(int aValue): m_value(aValue) {}
    operator int() { return m_value; }

    void print() const { std::cout << m_value; }
    bool isGreater(const Base& unEntier) const
    {
        return m_value > dynamic_cast<const Entier&>(unEntier).m_value;
    }
};
</code>

En plus, il faut définir les fonctions ''print'' et ''isGreater''. La fonction ''print'' se contente d'afficher le contenu de l'entier sur la console, la fonction ''isGreater'' est plus complexe. En effet, l'argument a comme type un type ''Base'' et non pas un type ''Entier''. Il va falloir convertir ce type vers un type ''Entier'' qui est un type hérité, c'est pour cela que nous faisons un ''dynamic_cast<const Entier&>(unEntier)'' qui va essayer de convertir si le paramètre ''unEntier'' hérite bien de ''Entier'' ou est un ''Entier''. Sinon, un exception ''std::bad_cast'' sera lancé si la conversion n'est pas possible.
 
</hidden>

==== Question n° 3.2 ====

Créer une fonction qui crée un tableau de ''theNumberOfValues'' entiers de type Entier

<code cpp>
std::vector<Base*> create_integer_array(
	size_t theNumberOfValues)
</code>
qui crée un tableau de ''theNumberOfValues'' valeurs commençant par la valeur ''0'' et se terminant à la valeur ''theNumberOfValues-1''.


<hidden Correction>

<code cpp>
std::vector<Base*> create_integer_array(size_t theNumberOfValues)
{
    std::vector<Base*> result;
    result.resize(theNumberOfValues);
    for (int i = 0; i < theNumberOfValues; i++)
        result[i] = new Entier(i);
    return result;
}
</code>

</hidden>

==== Question n° 3.3 ====

Créer une fonction qui crée un tableau de ''theNumberOfValues'' entiers de type ''Entier'' dont les éléments sont des nombres aléatoires compris entre ''theMinValue'' et ''theMaxValue''.

Cette fonction peut s’implanter comme suit. 
<code cpp> 
std::vector<Base*> create_random_integer_array(
	size_t theNumberOfValues, int theMinValue, int theMaxValue)
{
	std::random_device rd;
	std::mt19937 gen(rd());	
	std::uniform_int_distribution<> distr(theMinValue, theMaxValue);
	std::vector<Base*> array(theNumberOfValues);
	for (size_t i = 0; i < theNumberOfValues; i++)
		array[i] = new Entier(distr(gen));
	return array;
}
</code>

<hidden Correction>
La fonction initialise un générateur de nombre aléatoire ainsi qu'une distribution uniforme 
pour des entiers entre ''theMinValue'' et ''theMaxValue''. Elle utilise ensuite ce générateur
couplé à la distribution pour initialiser les ''theNumberOfValues'' éléments du tableau.

</hidden>
===== Question n°4 =====

Modifier la fonction de tri ''insertion_sort(std::vector<int>& anArray)'' afin de ne plus travailler sur des entiers mais sur des objets dérivant de la classe « abstraite » ''Base'' :

<code cpp>
void insertion_sort(std::vector<Base*>& anArray)
</code>

Tester la fonction avec le tableau d’entiers que vous avez créé à la question n°3.3.

<hidden Correction>
La seule ligne à modifier est relative à la comparaison, au lieu d'utiliser l'opérateur de comparaison ''>'', nous 
faisons un appel à la méthode ''isGreater'', ce qui donne le code suivant :

<code cpp>
void insertion_sort(std::vector<Base*>& anArray)
{
    for (int i = 0; i < anArray.size(); i++)
    {
        for (int j = i + 1; j < anArray.size(); j++)
        {
            if (anArray[i]->isGreater(*anArray[j]))
                std::swap(anArray[i], anArray[j]);
        }
    }
}
</code>

Pour tester, nous allons écrire la fonction suivante :

<code cpp>
void testTriEntier()
{
	std::vector<Base*> entiers = create_random_integer_array(10, -100, 100);
	print(entiers);
	std::cout << std::endl;
	insertion_sort(entiers);
	print(entiers);
	std::cout << std::endl;
}
</code>

</hidden>
===== Question n° 5 =====
Nous souhaitons étendre le code à une classe de réel.

==== Question n° 5.1 ====

Ecrire une nouvelles classe ''Reel'' qui dérive de ''Base'' et qui contient un champ  ''m_value'' de type ''double''.

==== Question n° 5.2 ====

Créer une fonction qui crée un tableau de ''theNumberOfValues'' objets de type ''Reel'' dont les éléments sont des nombres aléatoires compris entre ''theMinValue'' et ''theMaxValue''.

Cette fonction peut s’implanter comme suit. 
 
<code cpp>
std::vector<Base*> create_random_double_array(
	size_t theNumberOfValues, double theMinValue, double theMaxValue)
{
	std::random_device rd;
	std::mt19937 gen(rd());
	std::uniform_real_distribution<> distr(theMinValue, theMaxValue);
	std::vector<Base*> array(theNumberOfValues);
	for (size_t i = 0; i < theNumberOfValues; i++)
		array[i] = new Reel(distr(gen));
	return array;
}
</code>

Vérifier que l’algorithme de tri fonctionne aussi pour cette nouvelle nouvelle classe.

<hidden Correction>

Par analogie à la classe ''Entier'', nous créons la classe réel comme suit :

<code cpp>
class Reel : public Base
{
private:
    double m_value;
public:
    Reel() : m_value(0) {}
    Reel(double aValue) : m_value(aValue) {}
    operator double() { return m_value; }

    void print() const { std::cout << m_value; }
    bool isGreater(const Base& unReel) const
    {
        return m_value > dynamic_cast<const Reel&>(unReel).m_value;
    }
};

</code>

Pour tester, nous utiliserons une fonction similaire à la fonction suivante:

<code cpp>
void testTriReel()
{
	std::vector<Base*> reels = create_random_double_array(10, -1, 1);
	print(reels);
	std::cout << std::endl;
	insertion_sort(reels);
	print(reels);
	std::cout << std::endl;
}

</code>

</hidden>